How do we know if one algorithm is better than another? We could time them with a stopwatch, but that’s a flawed approach. The results would change depending on the computer's speed, the programming language, and even what other programs are running. We need a more universal way to measure efficiency.

Instead of measuring time in seconds, we measure how an algorithm’s performance changes as the size of its input grows. Does the runtime double when the input list doubles? Does it quadruple? This relationship between input size and performance is the key to understanding an algorithm's efficiency. This type of analysis is called asymptotic analysis.

To talk about these growth rates, computer scientists use a special set of notations. Think of them as shorthand for describing an algorithm's performance curve. The most common one is Big O notation.

Big O notation, written as $O(g(n))$, gives us a ceiling on an algorithm's performance. It says that for an input of size $n$, the runtime will be no worse than some constant multiple of $g(n)$. Imagine a speed limit sign. It tells you the maximum speed you can legally travel, but you can always go slower. Big O is that speed limit for an algorithm’s runtime.

Formally, we say $f(n) = O(g(n))$ if there are positive constants $c$ and $n_0$ such that for all $n \text{≥} n_0$:

While Big O gives us the upper bound (worst-case), Big Omega notation, written as $Ω(g(n))$, gives us the lower bound (best-case). If Big O is the speed limit, Big Omega is the minimum speed. It guarantees the runtime will be at least as fast as some constant multiple of $g(n)$.

Formally, we say $f(n) = Ω(g(n))$ if there are positive constants $c$ and $n_0$ such that for all $n \text{≥} n_0$:

Finally, there's Big Theta notation, written as $Θ(g(n))$. This is the most precise description. It means an algorithm's growth rate is tightly bound, both from above and below, by the same function $g(n)$. The runtime grows at the same rate as $g(n)$. This happens when the best-case and worst-case scenarios are the same.

Formally, we say $f(n) = Θ(g(n))$ if there are positive constants $c_1, c_2,$ and $n_0$ such that for all $n \text{≥} n_0$:

In practice, you'll hear

most often because developers are usually most concerned with the worst-case performance. It provides a reliable guarantee that the performance won't get any worse.

Many algorithms, especially those that are recursive, call themselves to solve smaller parts of a problem. A function that's defined in terms of itself is called a recurrence relation. For example, a function T(n) that splits a problem of size $n$ into two halves and does some constant work might be described like this:

To analyze these algorithms, we need to solve the recurrence relation to find a closed-form expression, like $T(n) = O(n \text{ log } n)$. There are three common methods for this.

For example, if we guess that the solution to $T(n) = 2T(n/2) + n$ is $O(n \text{ log } n)$, we would substitute this guess into the recurrence to show that it holds true.

3. The Master Theorem This is a powerful shortcut for solving a specific class of recurrence relations that follow a particular form.

Here, an algorithm divides a problem of size $n$ into $a$ subproblems, each of size $n/b$, and the cost of dividing the problem and combining the results is $f(n)$.

The Master Theorem provides a cookbook-style solution by comparing the function $f(n)$ with $n^{\log_b a}$. It presents three cases that determine the asymptotic bound of $T(n)$.

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $a f(n/b) \le c f(n)$ for some constant $c < 1$ and sufficiently large $n$, then $T(n) = \Theta(f(n))$.

While it looks complex, the Master Theorem simplifies analysis for many common divide-and-conquer algorithms, allowing you to bypass the more involved substitution or recursion tree methods.

Let's test your understanding of these concepts.

Understanding these methods of analysis is crucial. It lets you look at an abstract algorithm and predict its performance, helping you choose the right tool for the job without having to test every single option.