How can I tell the time complexity given this table of times?

user_14499442 0
Viewed 93

I have a question for you all.

I have a table of times and I am trying to figure out the time complexity of each function. The possible options for this table are O(n), O(1), O(n^2), O(n lg n).

enter image description here

Would I be corrent in saying that,

a = O(n^2), not sure how to motivate this one. But it doesn't seem to have such drastic times as c which I suspect must be O(lg n lg) then.

b = O(n), seems to have an even pattern where for every n = 100 it increases with 30 ms.

c = O(lg n lg), not sure how to motivate this one.

d = O(1), takes the same time no matter what n is.

How can I know for sure what time complexity it is just by looking at this time table? Thanks.

time java performance
3 Answers

I think (c) should be O(n^2) because from n=1000 to 500 the value is multiplied by 4. This matches with O(n^2) increase. For (a) however, n=1000 is just over two times that of n=500. This suggests that (a) is O(nlgn).

user_130915780

Input the table in excel, paint the graphs and compare it with this onetimes

a looks like O(n lg n), b is o(n), c O(n^2),

user_112609190

It helps to understand what O(n) actually means. To visualize it, make a simple line graph. Put 'n' on the X-axis, whatever n might be, and then put the complexity you're measuring on the Y axis. The aim is usually 'time complexity', so, time taken by a CPU to chug through the calculation for an input set with a given 'n' value.

If you actually did the experiment, for low 'n', the chart is just a gibberish smattering of arbitrary results; luck is the controlling factor, therefore, you can't make heads or tails of it (on that one test, your winamp switched songs, on this one test, the fact that arraylists start off with capacity for 10 means that at 11 you see a sudden spike, etcetera).

But, keep going. Eventually, and you have no idea how long this will take, but, eventually, a shape starts form. Either because you zoom out far enough (because your graph is very large, as it graphs from n=1 to n=100000), or because the algorithmic complexity 'took over' and is the controlling factor.

That's what O(n) measures: What does this graph's shape look like once it seems to stabilize? If you say an algorithm is O(n log n), you're saying: That right side of the graph will look a lot like the right side of the graph y = x * log(x).

This is also why O(n^2 + n) just isn't a thing - if you were to graph y = x^2 + x, it'll look exactly the same as y = x^2 does once you're far enough to the right. Given that the point is 'what is the shape', any factor that has no meaningful effect on the shape once you're far enough to the right, is irrelevant.

This gives you a very powerful tool to answer such questions. Get out a pen. Get out some paper. Go nuts graphing this. Seriously, get out a pen and do it: Draw a line, and put 10 tickmarks on the x axis, highlighting the 1st, 2nd, 5th, and 10th (for n=100, n=200, n=500, n=1000). Then, draw a y-axis from ~0-500, and draw a dot at x=100, y=33. Also at x=200, y=76, etcetera. Do your best to draw the 'trend line' on this. Then get out your graphing calculator or go to wolfram alpha and print the graph of y = x * ln(x).

If the shapes match, voila. You have your answer.

I'll give you one hint: You seem to think that the 'worst one' amongst the 4 options is O(n ln n). Maybe you should investigate the graphs of y=x^2 and y=x*ln(x) for a bit...

user_7686440
Related