Big-O introduction

Big-O notation describes how runtime or memory grows as input size n increases. We ignore constants and focus on dominant terms—same idea you glimpsed when comparing Python loops to NumPy vectorization.

Common complexities (slowest to fastest growth)

• O(1) — constant: index into array
• O(log n) — halving: binary search
• O(n) — linear: single loop over n items
• O(n log n) — efficient sorts, many divide-and-conquer algorithms
• O(n²) — nested loops over n
• O(2ⁿ) — exponential; brute-force subsets (avoid at large n)

Rules of thumb

• Drop constants: O(3n) → O(n)
• Keep dominant term: O(n² + n) → O(n²)
• Different inputs? O(a + b) when two arrays of different sizes

Count operations

#include 

int main() {
    int n = 8;
    int ops = 0;
    for (int i = 0; i < n; ++i) ops++;           // O(n)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) ops++;       // O(n^2)
    std::cout << "ops ~ n + n^2 = " << ops << "\n";
    return 0;
}

Important interview questions and answers

1. Q: Does Big-O measure exact seconds?
   A: No—it describes growth rate; hardware and constants still affect wall-clock time.
2. Q: Best vs worst vs average?
   A: Interviews often mean worst-case unless stated; hash maps average O(1) with rare O(n) worst case.

Self-check

1. Order O(1), O(n), O(n²) from fastest growing to slowest.
2. Why drop the constant in O(3n)?

Tip: Drop constants and lower-order terms—interviewers want dominant growth.