1

I am using quicksort, which is NLog(N), and have 20 items to sort.

Worst case is there for 26.02.... seconds? Really, seconds? I find that hard to believe, so what is the length measured in?

Nawlidge
  • 105
  • 1
  • 2
  • 9
  • Length of what? Do you mean time duration, or do you mean the input size? Big-O does not directly say anything about time duration, and what the input is must be specified (e.g. number of elements, number of bits, etc.). – jamesdlin Apr 03 '17 at 20:25
  • In terms of time. if I go 20Log20, it returns me 26.0... What does that 26 represent? – Nawlidge Apr 03 '17 at 20:28
  • @Nawlidge nothing, Big O says how something scales as N gets bigger, nothing more. It doesn't tell you anything specifc an trying to put concrete numbers into it is meaningless. – puhlen Apr 03 '17 at 20:30

2 Answers2

3

Big O Notation does not have units. It doesn't tell you how long something will take, nor does it tell you if an algorithm is fast or slow. All Big O tells you is how something scales as n changes.

Putting a number in for N does not have meaning for Big O, it's purpose is not to give you a number, but a trend of how quickly it will grow as N gets bigger. Imagine if you doubled N, to 40, your number would be a little more than twice as big. Take another algorithm, insertion sort, with O(N^2) complexity. the jump from 20^2 to 40^2 is huge, much more than doubling. So we can see that insertion sort will get proportionally slower compared to quicksort as N increases. And that's all you can learn from Big O, you can't say how fast either one will be, even relative to each other, for any specific N.

Keep in mind that Big O notation only looks at the highest order term. It ignores smaller terms and constant factors. N^2 + N is just N^2, because the first term overshadows the second. N + N + N is just N, because it still is just a linear increase, although it is steeper. N + 50 is just N, because the 50 is a constant factor that doesn't affect how it scales as N gets large.

puhlen
  • 8,400
  • 1
  • 16
  • 31
-1

Big O (in the sense of time complexity) tells you nothing about absolute durations. It just states how the maximum time required for solving a problem scales with the problem size. It is also restricted to large problem sizes (asymptotic behaviour).

That being said, it should be clear that it is a rather theoretical measure that does not neccessarily tell you something about actual software performance.

A few examples:

This is O(n) because time scales linearly with size:

n    1000  2000  3000  4000
t    5000 10000 15000 20000

This is O(n^2):

n    1000  2000  3000  4000
t    0.001 0.004 0.009 0.016

And finally this is O(1) but still has by far the the worst performance for problem sizes considered here:

n    1000  2000  3000  4000
t    1e100 1e100 1e100 1e100
Frank Puffer
  • 8,135
  • 2
  • 20
  • 45