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.

Jump to algorithms


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