You already know that Big O notation helps us talk about how an algorithm's runtime or memory usage grows with the input size. But a single Big O expression doesn't always tell the whole story. Real-world performance is often more nuanced, depending on the specific data an algorithm encounters.

Think about searching for a specific number in an unsorted list. If you get lucky, the number you're looking for is the very first element you check. That's the best case. If you're unlucky, it's the very last element, or maybe not in the list at all, forcing you to check every single one. That's the worst case. The average case is what happens most of the time—somewhere in the middle.

While the worst-case complexity is often the most important guarantee, understanding all three helps you make smarter choices. Sometimes, an algorithm with a poor worst-case performance is perfectly fine if its average case is excellent and the worst case is rare.

Analyzing iterative algorithms with nested loops is straightforward: you generally multiply their complexities. A loop running $n$ times that contains another loop running $n$ times results in $O(n^2)$ complexity.

Recursive algorithms are trickier. Each function call splits the problem into smaller subproblems. To analyze these, we can use a powerful tool called the Master Theorem for divide-and-conquer algorithms.

The theorem provides a cookbook-style solution by comparing the cost of the work done at each level, $f(n)$, with the rate at which new subproblems are created. It has three cases that tell you whether the final complexity is dominated by the work at the root, the work at the leaves, or the work distributed evenly across all levels of the recursion tree.

What's the complexity of adding an element to an array? You might say O(1), and you're usually right. But what happens when the array is full? You need to allocate a new, bigger array and copy all the old elements over. This resizing operation is O(n), which is very expensive.

If these expensive operations happened frequently, dynamic arrays would be terribly slow. Fortunately, they don't. This is where amortized analysis comes in. It helps us find the average cost per operation over a long sequence of operations.

For a dynamic array that doubles its size when full, the expensive O(n) copy happens at increasingly larger intervals. When we average that high cost over the many cheap O(1) additions that came before it, the cost per operation smooths out.

The result? The amortized time complexity for adding an element to a dynamic array is O(1). We accept a rare, slow operation in exchange for fast performance the rest of the time. This is a fundamental trade-off in data structure design.

The final piece of the puzzle is the classic space-time tradeoff. Often, you can make an algorithm run faster if you're willing to use more memory, or vice-versa.

Calculating the 40th Fibonacci number with a simple recursive function is incredibly slow because it calculates the same values over and over. But if we store each result after computing it the first time, the function becomes dramatically faster.

• Without Memoization: Time: $O(2^n)$, Space: $O(n)$ (for the recursion stack)
• With Memoization: Time: $O(n)$, Space: $O(n)$ (for the lookup table)

We traded extra space for a massive reduction in time. This principle appears everywhere, from database indexing to content delivery networks that cache web pages closer to users.

Analyzing an algorithm's efficiency is more than just a formula. It's about understanding how its performance changes with the structure of the input and making deliberate tradeoffs between time, memory, and implementation complexity.