Understanding Big-O Notation
Big-O Notation
Resources
Big-O Notation
Algorithm running times grow at different rates.
Big O doesn’t tell you the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows and establishes a worst-case run time.
A simple search on an array takes O(n) times, whereas a binary search would take O(log n) given the nature of (log[2]n).
Common Big-O Times
Here are five Big O run times that you’ll encounter a lot, sorted from fastest to slowest:
O(log n), also known as log time. Example: Binary search.O(n), also known as linear time. Example: Simple search.O(n * log n). Example: A fast sorting algorithm, like quicksort.O(n2). Example: A slow sorting algorithm, like selection sort.O(n!). Example: A really slow algorithm, like the traveling salesperson.
Big-O Time Complexity from Algorithms
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Selection Sort | Ω(n^2) | θ(n^2) | O(n^2) |
| Bubble Sort | Ω(n) | θ(n^2) | O(n^2) |
| Insertion Sort | Ω(n) | θ(n^2) | O(n^2) |
| Heap Sort | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) |
| Quick Sort | Ω(n log(n)) | θ(n log(n)) | O(n^2) |
| Merge Sort | Ω(n log(n)) | θ(n log(n)) | O(n log(n)) |
| Bucket Sort | Ω(n+k) | θ(n+k) | O(n^2) |
| Radix Sort | Ω(nk) | θ(nk) | O(nk) |