Algorithm Analysis

Combinatorics · Axiom Academy

How Recurrence Relations Power Modern Computing Imagine you're building a search feature for a music streaming app with 1 million songs. When a user types a song name, you need to find it instantly. How do you make this lightning-fast? You could check every song one by one (linear search), but that's slow. Instead, clever algorithms use a "divide-and-conquer" strategy that repeatedly splits the problem in half. But how much faster is it really? This is where recurrence relations become your secret weapon. That's 25,000 times faster! Let's discover why... Binary search works by repeatedly dividing the sorted list in half. Each step eliminates half of the remaining possibilities. Let's see this in action: Notice the pattern: each level of the tree represents one comparison. The number of levels is the total number of steps needed. Try adjusting the array size to see how the tree grows! Let's formalize this. If T(n) is the time to search an array of size n, we can express binary search as a recurrence relation: This means: to search n items, we do 1 comparison (constant work), then search half as many items. What do you think the solution to this recurrence is? Based on the pattern you observed in the tree visualization, what is T(n) equal to? Merge Sort: A Different Pattern Not all divide-and-conquer algorithms have the same recurrence. Let's compare merge sort, which sorts by dividing the array in half, sorting each half, then merging them:

This is the written version of the interactive lesson above. See the full Combinatorics course.