O(n log n)

[bnewman]

Big O notation is used to describe how efficiently algorithms scale as the input grows.  O(n log n), pronouced "big O of n log n", is one class that contains the most common sorting algorithms.

lyrics by Benjamin Newman

ttto: "Blowin' in the Wind" by Bob Dylan

 

listen to this song

 

/: D G D (Bm) / (D) G A - :/

 

How many times must two strings be compared

To sort alphabetically?

And how long does it take to empty a heap

Or fill up a binary tree?

If you store every bit string between 1 and n

How many bits will that be?

 

/ G A D Bm / G A D - /

 

The answer, my friends, is O(n log n)

The answer's O(n log n)