CODEWITHSUNDEEP
performancemathbig-otime-complexity
Franklin Cho
Franklin Cho

Reputation: 21

Empirically determining the big-O runtime of a program?

How would we be able to guess the big-O speed of a program given that we have the values of n and corresponding running times? Mind you, I do not come from a CS background and I have done some reading to put things in context, but am utterly clueless at this point.

Upvotes: 2

Views: 464

Answers (3)

gnasher729
gnasher729

Reputation: 52538

You can find it mathematically (which is the way guaranteed to give a correct result, unless you make mistakes which many do), or empirically (by doing measurements). The second method will often give the right results but can be tricked.

For an empirical result, I'd start with n = 1 to n = 10, then continue growing n by 10% each time, drawing a chart, until it takes too long. Algorithms using memory proportional to n often have a "jump" in execution time when your memory requirements go to the next cache level; increasing n by 10% means you can find these jumps.

And then there are algorithms where tiny changes in the data make huge differences in timing. For an NP-complete problem, some instances of the same problem can be very easy to solve, and some can be very hard. Or matrix multiplication, where the obvious (and slow) algorithm can have a huge variation in execution time depending on n.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372814

There is no general procedure for doing this that will always work, but there are many techniques that are powerful in general.

Let's assume that your program's runtime has one of the following "standard" forms:

  • Polynomial: O(nk)
  • Exponential: O(an)

If it does have one of these forms, here are some useful techniques for determining the constants controlling the big-O expression.

Polynomial time

If your function has runtime O(nk), then (for large n) the runtime will approximately be of the form T(n) = c·nk. A really useful technique for figuring out what c and k are is to use a log-log plot. Suppose that you look at the values of log T(n) and log (c · nk). Note that

log (c · nk) = log c + k log n

This means that if you have a log-log plot, where the dependent variable is log T(n) and the independent variable is log n, then any polynomial will come out as a line. You can then use any standard linear regression technique to get a best-fit line that matches the line, from which you can recover log c and k in the above expression. From there, the runtime of your algorithm will be O(nk)

Exponential Time

If your runtime is exponential (that is, O(an) for some a), then you can use a standard log plot to recover the base a. If your function is approximately T(n) = c · an for some constants a and c, then taking the log of the right-hand side gives you

log (c · an) = log c + n log a

This means that if you plot T(n) versus log c + n log a, you'll get back some straight line. You can then do a regression to recover log c and log a, from which the runtime can be read off as O(an).

Hope this helps!

Upvotes: 1

Assaf Karmon
Assaf Karmon

Reputation: 923

There is really nothing that anyone can tell you that will help you answer a similar question in the future. I suggest that you read this book Intro to algorithms and try to understand the concept, if you need to answer these kind of questions in interviews, it may be a good use of your time.

Upvotes: 1

Related Questions