2

My program of sorting values clocks at:

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

Is that O(n)?

3
  • 1
    That's a rather small sample size to make any conclusions about with any certainty. You'll need more to perform a proper statistical analysis.
    – outis
    Nov 13, 2009 at 16:00
  • @outis: Do you mean that the O() for 1000000000 values could deviate despite a stable O(n) for these samples?
    – sharkin
    Nov 13, 2009 at 16:05
  • 3
    That's exactly what he means :) It could be logarithmic. Recall a logarithm graph. If you break it down into enough sections, they can be represented linearly with ease. Who's to say the next value for 1000000000 isn't 5000000000s ?
    – Pod
    Nov 13, 2009 at 16:10

8 Answers 8

17

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?

6
  • It could be a radix sort, of course - but I agree, a general purpose O(n) sort is somewhat suspicious :)
    – Jon Skeet
    Nov 13, 2009 at 15:43
  • 3
    +1 Landau notation applies to algorithms not programs. Nov 13, 2009 at 15:47
  • @nojo: I use std::sort (introsort?) with random values (stdlib::rand()) in the span 0-10000. I guess those facts would have to go as presumtions for the O(n) of these samples?
    – sharkin
    Nov 13, 2009 at 16:09
  • Hmm - I would have guessed that you weren't using random input - I'm not sure that O(n) is possible for a sort of random input (like Jon Skeet said), though your results certainly look like it. Digging deeper into Jon Skeet's comment, radix sort can appear to be O(n) (en.wikipedia.org/wiki/Radix_sort), so that might be what you're seeing.
    – nojo
    Nov 13, 2009 at 16:24
  • 1
    It still could be that the element size is small enough that the n log n portion of its calculation hasn't taken over yet.
    – T.E.D.
    Nov 13, 2009 at 16:30
10

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.

6
  • 1
    Generally: you make the input n times bigger, it takes n times longer.
    – Stephan202
    Nov 13, 2009 at 15:34
  • @Stephan202: Indeed - I was just going by the example numbers given.
    – Jon Skeet
    Nov 13, 2009 at 15:35
  • (I've updated the answer to make that clearer though - thanks.)
    – Jon Skeet
    Nov 13, 2009 at 15:42
  • Yup: if the time is dominated enough by something like I/O, the algorithm could be bogosort (which is O(n!n) for average performance). Nov 13, 2009 at 16:17
  • I didn't downvote. However, I didn't upvote either because I fear you may be feeding his delusion that one can derive the time behavior of an algorithim from three data points. Perhaps that had something to do with it?
    – T.E.D.
    Nov 13, 2009 at 16:37
8

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.

4

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.

alt text

2

it looks like O(n) to me.

2

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

1000000 = 10 * 100000

and

82s = 10 * 8s (roughly)
0
2

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.

1

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.