What is Big-O
In computer science, Big-O represents the efficiency or performance of an algorithm. Big-O makes it easy to compare algorithm speeds and gives you a general idea of how long it will take the algorithm to run. The term “Big-O” is typically used to describe general performance, but it specifically describes the “worst case” (i.e. slowest) speed the algorithm could run in.
When it comes to comparison sorting algorithms, the
n in Big-O notation represents the amount of items in the array that’s being sorted. This means that if you’re sorting an array of 5 items,
n would be 5. If you were sorting 100 items
n would be 100.
Best, Average, and Worst Case
Comparison algorithms always come with a best, average, and worst case. These essentailly represent how fast the algorithm could perform (best case), how slow it could perform (worst case), and how fast you should expect it to perform (average case).
All comparison algorithms require that every item in an array is looked at at least once. This means, that the best any comparison algorithm can perform is O(n). However, this kind of performance can only happen if the algorithm is already sorted.
|Heapsort||nlog (n)||nlog (n)||nlog (n)|
|Merge Sort||nlog (n)||nlog (n)||nlog (n)|
|Quicksort||nlog (n)||nlog (n)||n2|
|Shellsort||nlog (n)||n (log(n))2||n (log(n))2|