Big O Deep Dive

By the end, you can

• State the formal definition of Big O and explain the role of the constants c and n₀.
• Simplify a multi-term expression like 6n² + 3n + 100 to its Big-O class, identifying the dominant term and dropping constants and lower-order terms (→ O(n²)).
• Explain why the logarithm base is omitted in O(log n).
• Rank O(1), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ) by growth rate and give a representative algorithm for each (array index, binary search, linear scan, merge sort, nested loops, brute-force subsets).
• Calculate the approximate step count for each class at a given n (e.g. n = 1,000).
• Distinguish Big O (upper bound), Big Omega (lower bound), and Big Theta (tight bound), and state which one a given performance claim is actually using.
• Correct the myth that Big O always means worst case, and give a valid best-case Big-O bound as an example (e.g. O(1) when linear search hits the target on its first comparison).