What's my Big O?

Question

My program of sorting values clocks at:

• 100000 8s
• 1000000 82s
• 10000000 811s

Is that O(n)?

Answer 1

it looks like O(n) to me.

Answer 2

Yes, that looks like O(n) to me - going from the 1st to 2nd case and the 2nd to 3rd case, you've made the input 10 times bigger, and it's taken 10 times longer.

In particular, it looks like you can predict the rough time by using:

f(n) = n / 12500

or

f(n) = n * 0.00008

which gives a simplest explanation of O(n) for the data provided.

EDIT: However... As has been pointed out, there are various ways in which the data could be misleading you - I rather like Dennis Palmer's idea that the IO cost is dwarfing everything else. For example, suppose you have an algorithm whose absolute number of operations is:

f(n) = 1000000000000n + (n^2)

In that case the complexity is still O(n^2), but that won't become apparent from observations until n is very large.

I think it would be accurate to say that these observations are suggestive of an O(n) algorithm but that doesn't mean it definitely is.

Answer 3

Looks like it, but in reality, you really need to analyze the algorithm, because there may be different cases based on the data. Some algorithms do better or worse with pre-sorted data, for instance. What's your algorithm?

Answer 4

Yes, that is O(n) because it scales with the number of items.

1000000 = 10 * 100000

and

82s = 10 * 8s (roughly)

Answer 5

Time behavior doesn't work that way. All you can really say there is that those three datasets are roughly O(n) from each other. That doesn't mean the algorithim is O(n).

The first problem is that I could easily draw a curve that goes exponential ( O(e**n) ) that nonetheless includes those three points.

The big problem though is that you didn't say anything about the data. There are many sorting algorithms that approach O(n) for sorted or nearly sorted inputs (eg: Mergesort). However, their average case (typically randomly-ordered data) and worst case (often reverse-sorted data) is invariably O(nlogn) or worse.

Answer 6

Yes, it appears to be O(n), but I don't think you can conclusively analyze the algorithm based on it's timed performance. You might be using the most inefficient sorting algorithm, but have O(n) timed results because the data read/write time is the majority of the total execution time.

Edit: Big-O is determined by how efficient an algorithm is and how it scales. It should predict the growth of execution time as the number of input items grows. The inverse is not necessarily true. Observing a given growth in execution time could mean a few different things. If it stays true to the example numbers you've given, then you can conclude that your program runs at O(n), but as others have said, that doesn't mean your sorting algorithm is O(n).

Answer 7

You cannot depend on that to say it is O(n). Bubblesort, for instance, can complete in n steps, however it is an O(n^2) algorithm.

Answer 8

You cannot tell.

First, the time depends on the data, environment and algorithm. If you have an array of zeroes and try to sort it, the program running time shouldn't be much different for 1000 or 1000000 elements.

Second, the O notation tells about function behavior for big value of n, starting at n0. It could be that your algorithm scales well up to certain input size, and then its behavior changes - like the g(n) function.