89

So I think I'm going to get buried for asking such a trivial question but I'm a little confused about something.

I have implemented quicksort in Java and C and I was doing some basic comparissons. The graph came out as two straight lines, with the C being 4ms faster than the Java counterpart over 100,000 random integers.

Results

The code for my tests can be found here;

android-benchmarks

I wasn't sure what an (n log n) line would look like but I didn't think it would be straight. I just wanted to check that this is the expected result and that I shouldn't try to find an error in my code.

I stuck the formula into excel and for base 10 it seems to be a straight line with a kink at the start. Is this because the difference between log(n) and log(n+1) increases linearly?

Thanks,

Gav

3
  • 3
    Google image search seems surprisingly good on searched such as "n log n". Commented Jun 8, 2009 at 16:49
  • 1
    The Java line on top doesn't look straight to me.
    – Puppy
    Commented Jun 6, 2010 at 11:59
  • 1
    Similar, indeed, which is why it's referred to as "linearithmic time"
    – msanford
    Commented Nov 13, 2013 at 19:43

7 Answers 7

88

Make the graph bigger and you'll see that O(n logn) isn't quite a straight line. But yes, it is pretty near to linear behaviour. To see why, just take the logarithm of a few very large numbers.

For example (base 10):

log(1000000) = 6
log(1000000000) = 9
…

So, to sort 1,000,000 numbers, an O(n logn) sorting adds a measly factor 6 (or just a bit more since most sorting algorithms will depend on base 2 logarithms). Not an awful lot.

In fact, this log factor is so extraordinarily small that for most orders of magnitude, established O(n logn) algorithms often outperform linear time algorithms. A prominent example is the creation of a suffix array data structure.

A similar case has recently bitten me when I tried to improve a quicksort sorting of short strings by employing radix sort. Short strings, this (linear time) radix sort was faster than quicksort, but there was a tipping point for still relatively short strings, since radix sort crucially depends on the length of the strings you sort.

3
  • 1
    Good sorts tend to go for a linear algorithm once they have divided and conquered into sufficiently small pieces. Exactly how small is a matter of benchmarking (real data). Commented Jun 8, 2009 at 16:48
  • 2
    Tom: I'm not sure what exactly you mean by linear. Often, sorting algorithms do the opposite, using O(n^2) sortings such as insertion sort on small portions, since their constant factor is so small that even quadratic runtime outperforms nlogn sorting. On the other hand, introsort uses a strategy to break out of too deep recursions – but again, this isn't anywhere linear, it just exchanges a quadradic worst case for O(n logn) behaviour. Commented Jun 8, 2009 at 19:40
  • its impossible to do comparison based linear sorts Commented May 9 at 4:15
13

FYI, quicksort is actually O(n^2), but with an average case of O(nlogn)

FYI, there is a pretty big difference between O(n) and O(nlogn). That's why it's not boundable by O(n) for any constant.

For a graphical demonstration see:

O(n) vs O(nlogn)

3
  • 2
    a) Without specifying, O() is usually used to denote the expected (average) complexity. b) O() notation doesn't include constant factors, so O(n) and O(2n) are the same. Since log(n) is nearly constant (for large numbers, compared to n), it can be said that O(n) and O(n log(n)) are nearly the same. You should have plotted: wolframalpha.com/input/?i=plot+7+x%2C+x+log+x+from+1+to+1500
    – Timmmm
    Commented Mar 24, 2010 at 18:06
  • 16
    This is generally untrue. Big O notation typically denotes worst case asymptotic complexity, and it notates a function which bounds above the algorithms complexity. O(n) does not approximate O(nlogn), although for practical purposes O(nlogn) is relatively good and not much worse. The worst case performance of quick sort is certainly not an uncommon thing to encounter. Try doing a quicksort on the entries in the dictionary if you don't believe me.
    – groundhog
    Commented Apr 8, 2010 at 1:39
  • I do not thing there is a big difference. Especially when you compare it to the next order $O(n^2)$. i.sli.mg/9zXUQR.png Commented Sep 25, 2016 at 5:03
6

For even more fun in a similar vein, try plotting the time taken by n operations on the standard disjoint set data structure. It has been shown to be asymptotically n α(n) where α(n) is the inverse of the Ackermann function (though your usual algorithms textbook will probably only show a bound of n log log n or possibly n log* n). For any kind of number that you will be likely to encounter as the input size, α(n) ≤ 5 (and indeed log* n ≤ 5), although it does approach infinity asymptotically.

What I suppose you can learn from this is that while asymptotic complexity is a very useful tool for thinking about algorithms, it is not quite the same thing as practical efficiency.

3
  1. Usually the O( n*log(n) ) algorithms have a 2-base logarithmic implementation.
  2. For n = 1024, log(1024) = 10, so n*log(n) = 1024*10 = 10240 calculations, an increase by an order of magnitude.

So, O(n*log(n)) is similar to linear only for a small amount of data.

Tip: don't forget that quicksort behaves very well on random data and that it's not an O(n*log(n)) algorithm.

4
  • 3
    All logarithms are the same, they differ only in scale. So I don't see the significance of your first statement. Also, I don't agree with your statement that O(n log n) only similar to linear for a small amount of data. Once again, it's a scaling thing. As a counter-example, just look at the graphs in the original question.
    – waxwing
    Commented Jun 7, 2009 at 19:54
  • I don't mean graphically similar (to a straight line) but time-complexity similar. O(nlogn) time can easily be an order of magnitude bigger than O(n). If the graphs compared O(nlogn) and O(n) algorithms you would see what I mean. :) As the N goes bigger and bigger the O(nlogn) *moves to next logarithimic scales. Commented Jun 7, 2009 at 20:34
  • 1
    On average Quicksort IS an O(n log n) algorithm.
    – Manu
    Commented Aug 12, 2010 at 13:05
  • The first point is wrong, as stated by @waxwing. By dividing the limits of different bases you can prove that changing the log base only effects the complexity by a constant factor - the log base is irrelevant from a complexity perspective. As for the conclusion, as the number of elements increase the shapes of the linear and log-linear lines will become more similar, not less.
    – mateor
    Commented Jun 2, 2015 at 20:31
2

Any data can be plotted on a line if the axes are chosen correctly :-)

Wikipedia says Big-O is the worst case (i.e. f(x) is O(N) means f(x) is "bounded above" by N) https://en.wikipedia.org/wiki/Big_O_notation

Here is a nice set of graphs depicting the differences between various common functions: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

The derivative of log(x) is 1/x. This is how quickly log(x) increases as x increases. It is not linear, though it may look like a straight line because it bends so slowly. When thinking of O(log(n)), I think of it as O(N^0+), i.e. the smallest power of N that is not a constant, since any positive constant power of N will overtake it eventually. It's not 100% accurate, so professors will get mad at you if you explain it that way.

The difference between logs of two different bases is a constant multiplier. Look up the formula for converting logs between two bases: (under "change of base" here: https://en.wikipedia.org/wiki/Logarithm) The trick is to treat k and b as constants.

In practice, there are normally going to be some hiccups in any data you plot. There will be differences in things outside your program (something swapping into the cpu ahead of your program, cache misses, etc). It takes many runs to get reliable data. Constants are the biggest enemy of trying to apply Big O notation to actual runtime. An O(N) algorithm with a high constant can be slower than an O(N^2) algorithm for small enough N.

1
  • (I'm assuming you meant a straight line, and not "line" as a general term for curve.) I would buy that any continuously differentiable, real-valued function of a real variable can be plotted on a straight line if the axes are chosen correctly with only moderate shenanigans like duplicate axis values (needed unless it's a one-to-one function), but "any data"? I think that's a stretch. How about the function that's zero for all rational numbers but one for all irrational numbers. (It's known as the Dirichlet function, and it's a true mathematical function.)
    – Sarah G
    Commented Jul 7, 2014 at 4:54
1

log(N) is (very) roughly the number of digits in N. So, for the most part, there is little difference between log(n) and log(n+1)

2
  • 3
    log-base-10 is very roughly the number of digits in N (assuming you're using the decimal representation). Most sort/search algorithms would be using log-base-2 which, while proportional to log-base-10 (so the big-O still applies), is nothing like what you describe :-)
    – paxdiablo
    Commented Jun 8, 2009 at 1:45
  • 2
    Another way to say it is that log-base-2 is roughly the number of digits in N when written in binary, aka the number of bits required to represent N. Commented Aug 2, 2009 at 16:33
0

Try plotting an actual linear line on top of it and you'll see the small increase. Note that the Y value at 50,0000 is less than the 1/2 Y value at 100,000.

It's there, but it's small. Which is why O(nlog(n)) is so good!

1
  • It's still a damn sight better than O(n^2).
    – paxdiablo
    Commented Jun 8, 2009 at 1:46

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