Big O Notation
š Time Complexity Breakdown
O(1) - Constant time: "Instant" ā same time no matter the size. Example: Accessing an array element by index.
O(log n) - Logarithmic time: "Divide & conquer" ā shrink the problem fast. Example: Binary search.
O(n) - Linear time: "One loop" ā check each item once. Example: Loop through a list.
O(n log n) - Linearithmic time: "Smart sorting" ā break & conquer, then combine. Example: Merge sort, heap sort.
O(nĀ²) - Quadratic time: "Double loop" ā compare every pair. Example: Bubble sort, nested loops.
O(nĀ³) - Cubic time: "Triple loop" ā deep nested processing. Example: 3D matrix operations.
O(2āæ) - Exponential time: "Explodes" ā doubles with each step. Example: Recursive Fibonacci, brute-force combos.
O(n!) - Factorial time: "Total chaos" ā try every possible order. Example: Solving permutations (e.g. traveling salesman).
Context: A comparison of common time complexities, their descriptions, and practical examples.
š Quick Order to Remember (from Fastest ā Slowest)
$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$
š§ Mnemonic (Optional Fun One)
"One Lazy Nerd Sorts Squares, Cubes, and Explodes Fast!"
($1$, $\log n$, $n$, $n \log n$, $n^2$, $n^3$, $2^n$, $n!$)