W2232 Big-O Notation
- Watch Introduction to Big O Notation and Time Complexity (CS Dojo)
- Watch Getting Sorted & Big O Notation (Computerphile)
- Read A beginner's guide to Big O notation (Rob Bell)
- Watch Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation (Tom Scott)
Big-O Notation is used to describe the performance of an algorithm and establishes a worst-case run time. It calculates the number of operations performed and the memory required for an algorithm to conclude. There are different formulas to calculate the operations performed and memory requirements for each sorting algorithm. Big-O Notation is unable to tell you how long an algorithm will run because there are too many factors that influence the time an algorithm takes to run.
O(log n) - Binary Search
O(n) - Simple Search/ Bubble Sort
O(n * log n) - Quicksort
O(n2) - Insertion Sort/Selection Sort
|O(log(n))||Logarithmic||Divide in half / Binary search|
|O(n * log(n))||Linearithmic||Effective sorting algorithm|
Big-O Notation can also be calculated by hand. You can go through each line of code and determine if it will be "1", "log(n)", n, etc. You can then add all of the growth rates together and it can be expressed as, for example, O(1+3n) where the "1" represents one line of O(1), and the "3n" represents 3 lines of O(n).
Big-O Notation for Beginners (AdrianMejia)
Big-O Notation (Wikipedia)