Big-O Notation (Quick Summary)

Big-O is the notation used to describe the "Worst-Case" time or space required by an algorithm as the data size (n) increases.

Growth Rates (from fastest to slowest)

1. O(1) - Constant: Fastest. Regardless of data size, the time remains the same (e.g., accessing array[0], reading a value from a Hash Map).
2. O(log n) - Logarithmic: Discards half of the data at each step (e.g., Binary Search, searching in a Binary Search Tree).
3. O(n) - Linear: Directly proportional to the data size. Requires looping through every item (e.g., finding Max/Min in an unsorted Array).
4. O(n log n) - Linearithmic: Efficient sorting (e.g., Merge Sort, Quick Sort).
5. O(n^2) - Quadratic: Nested loops (e.g., Bubble Sort, Insertion Sort, comparing every pair).
6. O(2^n) - Exponential: Branches out for every possibility (e.g., Recursive Fibonacci without Memoization).
7. O(n!) - Factorial: Slowest. Permutes all possibilities (e.g., Traveling Salesman Problem using Brute Force).

Simple Calculation Rules (Rules of Thumb)

• Drop constants: O(2n + 5) -> O(n)
• Keep only the fastest-growing term: O(n^2 + n + log n) -> O(n^2)
• Add when steps are sequential: 2 separate loops O(n) + O(n) = O(n)
• Multiply when nested: Nested loops O(n) * O(n) = O(n^2)