2

I'm measuring the execution time of a program that should run in O(n^2). To get the expected running time I would calculate n^2 from the input size I assume. But I taken the execution time using another program I get the time in milliseconds. So my question is how to compare that to n^2. For n^2 I get a larger number. How would I convert this to miliseconds? I know this question may not be worded as good as you might like. Hopefully, you know what I mean.

jax
  • 728
  • 1
  • 11
  • 31
  • 1
    It doesn't. http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1 – reem Jan 26 '14 at 02:27

3 Answers3

2

It doesn't measure time in any unit. It describes how the time will change if n changes.

For example, O (n^2) is defined to mean: "There is a constant c such that the time is at most c * n^2 for all but the first few n". When you run the algorithm on different computers, it could be 5 n^2 nanoseconds on one, and 17 n^2 milliseconds on another computer. You just have c = 5 nanoseconds in one case, c = 17 milliseconds in the other case.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
1

Big O doesn't measure a unit of time. It expresses the runtime of the code in terms of input of size n. You can't accurately use a big O notation to compute runtime in milliseconds as this may vary per machine that you run the code on.

You can estimate how long it takes if you know the runtime of each of the operations in the algorithm but that's not really what the big O notation is meant for.

Simeon Visser
  • 118,920
  • 18
  • 185
  • 180
  • "It expresses the runtime" >.> – U2EF1 Jan 26 '14 at 02:32
  • @U2EF1: yes, in an abstract sense. The relation between big O notation and actual execution time is very architecture-specific. So you can only answer the question when you know a lot more beyond the big O info. – Simeon Visser Jan 26 '14 at 02:33
  • Then is there a way to estimate the runime in milliseconds from a program such as the 'time' untility in linux. – jax Jan 26 '14 at 03:39
  • You could measure execution time for various values of n and base your estimates on that. – Simeon Visser Jan 26 '14 at 03:58
  • @user246694 Sometimes. That extrapolation will probably only be relevant as you stay within certain memory bounds, for instance you can see sudden performance changes when you accidentally hit cache line multiples, there is a huge drop off when you start swapping, &c. An actual algorithm meant to handle wildly different `n` will normally have to be pretty complicated. And of course there are no asymptotes in the real world. – U2EF1 Jan 26 '14 at 04:17
1

It bounds (to within a constant factor) the asymptotic runtime in numbers of steps of an abstract model of a computer, often a Register Machine.

U2EF1
  • 12,907
  • 3
  • 35
  • 37