Math for coding interviews/What Big-O actually means
What Is Big-O Notation? (No Formulas)
Big-O describes how the number of operations grows as input size n grows. It ignores constants and lower-order terms because for large n they become irrelevant. O(2n) and O(n) are the same class. O(n² + n) simplifies to O(n²). We only care about the dominant term.
See it for yourself
A graph with n on the x-axis and "operations" on the y-axis. Multiple curves. As n grows large, O(n²) dwarfs O(n log n) which dwarfs O(n). The constants (2n vs 5n) are invisible at large scale.
What Big-O actually means
Big-O describes how the number of operations grows as input size n grows. It ignores constants and lower-order terms because for large n they become irrelevant. O(2n) and O(n) are the same class. O(n² + n) simplifies to O(n²). We only care about the dominant term.
Think of it this way: Long-term salary comparison. A job paying $50k + $1k/year raise versus a job paying $30k + 10% compound raise. Early on $50k is better. After ~10 years, the percentage-growth job overtakes it and keeps growing faster. Big-O is like asking "which job pays more after 20 years?" - the initial salary becomes irrelevant.
For algorithms: Big-O is the universal language interviewers use to compare solutions. A solution might be faster for small inputs but worse for large ones. Big-O captures the long-term behavior.
Real-world analogy
Long-term salary comparison. A job paying $50k + $1k/year raise versus a job paying $30k + 10% compound raise. Early on $50k is better. After ~10 years, the percentage-growth job overtakes it and keeps growing faster. Big-O is like asking "which job pays more after 20 years?" - the initial salary becomes irrelevant.
Why it matters in interviews
Big-O is the universal language interviewers use to compare solutions. A solution might be faster for small inputs but worse for large ones. Big-O captures the long-term behavior.