Big-O
Big-O provides everything you need to know about the algorithms used in computer science. Learn about each algorithm's Big-O behavior with step by step guides and code examples written in Java, Javascript, C++, Swift, and Python.
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.
What is n
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.
Algorithms
Comparison Sort
Algorithm | Best | Average | Worst |
---|---|---|---|
Bubble Sort | n | n2 | n2 |
Cycle Sort | n2 | n2 | n2 |
Heapsort | n | log (n)n | log (n)n | log (n)
Insertion Sort | n | n2 | n2 |
Merge Sort | n | log (n)n | log (n)n | log (n)
Quicksort | n | log (n)n | log (n)n2 |
Selection Sort | n2 | n2 | n2 |
Shellsort | n | log (n)n (log(n))2 | n (log(n))2 |
Non-Comparison Sort
Algorithm | Best | Average | Worst |
---|---|---|---|
Radix Sort | nk | nk | nk |