Big-O, Big-Theta & Big-Omega in Practice

In casual conversation, "Big-O" gets used as a catch-all for "how fast is this," but there are technically three related notations, and each one asserts something slightly different about an algorithm. Knowing the difference sharpens exactly what claim is being made - and interviewers notice when a candidate reaches for the right one.

• -Big-O (O): an upper bound - this algorithm never does more than roughly this much work. Usually describes the worst case.
• -Big-Omega (Ω): a lower bound - this algorithm never does less than roughly this much work. Usually describes the best case.
• -Big-Theta (Θ): a tight bound - the upper and lower bounds match, meaning this is what actually happens regardless of the specific input, not just a ceiling or a floor.

Linear search is a clean example of why these differ. In the worst case (the target is missing, or sits at the very last index), linear search is O(n) - it must check every element. In the best case (the target is the first element checked), it is Ω(1) - one comparison and done. Because the best case and worst case genuinely differ, linear search has no single Θ bound that applies to every input; only O(n) and Ω(1) can be claimed separately.

A summing function that always adds up every element of a list, with no early exit, behaves differently: it is O(n), Ω(n), and Θ(n) all at once, because the best case and worst case are identical - there is no lucky input that finishes early. In interviews, O is what gets asked for almost every time, because the worst case is the one that determines whether a system holds up under adversarial or unlucky input, which is exactly the case that matters in production.

• -O(1) - constant time. Example: reading a value out of a dict by key, or accessing a list by index.
• -O(log n) - logarithmic time. Example: binary search, which throws away half of the remaining search space on every step.
• -O(n) - linear time. Example: scanning a list once to find its maximum.
• -O(n log n) - linearithmic time. Example: an efficient comparison sort like merge sort, covered in a later tier.
• -O(n²) - quadratic time. Example: comparing every pair of elements with two nested loops.
• -O(2^n) - exponential time. Example: the naive recursive Fibonacci function later in this tier, which re-explores the same subproblems over and over.