How to solve T(n) = 5T(n/2) + O(nlogn) using recursion

So that might be silly, but I'm stuck with this recursion T(n) = 5T(n/2) + O(nlogn). I know from Master Theorem that it's supposed to be , but I can't really get there.

So far I got to a point of

I just wanted to know if I'm going the right direction with that

You're definitely on the right track here! Let's see if we can simplify that summation.

First, notice that you can pull out the log n term from the summation, since it's independent of the sum. That gives us

(n log n) (sum from k = 0 to lg n (5/2)^k)

That sum is the sum of a geometric series, so it solves to

((5/2)^{log n + 1} - 1) / (5/2 - 1)

= O((5/2)^{lg n})

Here, we can use the (lovely) identity that a^{log_b c} = c^{log_b a} to rewrite

O((5/2)^{lg n}) = O(n^{lg 5/2})

= O(n^{lg 5 - 1})

And plugging that back into our original formula gives us

n log n · O(n^{lg 5 - 1}) = O(n^{lg 5} log n).

Hmmm, that didn't quite work. We're really, really close to having something that works here, though! A good question to ask is why this didn't work, and for that, we have to go back to how you got that original summation in the first place.

Let's try expanding out a few terms of the recurrence T(n) using the recursion method. The first expansion gives us

T(n) = 5T(n / 2) + n log n.

The next one is where things get interesting:

T(n) = 5T(n / 2) + n log n

= 5(5T(n / 4) + (n / 2) log (n / 2)) + n log n

= 25T(n / 4) + (5/2) log (n / 2) + n log n

Then we get

T(n) = 25T(n / 4) + (5/2) log (n/2) + n log n

= 25(5T(n / 8) + (n / 4) log (n / 4)) + (5/2) log (n/2) + n log n

= 125T(n / 8) + (25/4)n log (n / 4) + (5/2) log (n/2) + n log n

The general pattern here seems to be the following sum:

T(n) = sum from i = 0 to lg n (5/2)^kn lg(n/2^k)

= n sum from i = 0 to lg n (5/2)^k lg(n/2^k)

And notice that this is not your original sum! In particular, notice that the log term isn't log n, but rather a function that grows much more slowly than that. In fact, as k gets bigger, that logarithmic term gets much, much smaller. In fact, if you think about it, the only time we're really paying the full lg n cost here is when k = 0.

Here's a cute little trick we can use to make this sum easier to work with. The log function grows very, very slowly, so slowly, in fact, that we can say that log n = o(n^ε) for any ε > 0. So what what happens if we try upper-bounding this summation by replacing lg (n / 2^k) with (n / 2^k)^ε for some very small but positive ε? Well, then we'd get

T(n) = n sum from i = 0 to lg n (5/2)^k lg(n/2^k)

= O(n sum from i = 0 to lg n (5/2)^k (n / 2^k)^ε)

= O(n sum from i = 0 to lg n (5/2)^k n^ε (1 / 2^ε)^k)

= O(n^1+ε sum from i = 0 to lg n (5 / 2^1+ε))

This might have seemed like some sort of sorcery, but this technique - replacing logs with tiny, tiny polynomials - is a nice one to keep in your back pocket. It tends to come up in lots of contexts!

The expression we have here might look a heck of a lot worse than the one we started with, but it's about to get a lot better. Let's imagine that we pick ε to be sufficiently small - say, so that that 5 / 2^1+ε is greater than one. Then that inner summation is, once again, the sum of a geometric series, and so we simplify it to

((5/2^1+ε)^{lg n + 1} - 1) / (5/2^1+ε - 1)

= O((5/2^1+ε)^{lg n})

= O(n^{lg (5/21+ε)}) (using our trick from before)

= O(n^{lg 5 - 1 - ε})

And that's great, because our overall runtime is then

T(n) = O(n^1+ε n^{lg 5 - 1 - ε})

= O(n^{lg 5}),

and you've got your upper bound!

To summarize:

• Your original summation can be simplified using the formula for the sum of a geometric series, along with the weird identity that a^{log_b c} = c^{log_b a}.

• However, that won't give you a tight upper bound, because your original summation was slightly off from what you'd get from the recursion method.

• By repeating the analysis using the recursion method, you get a tighter sum, but one that's harder to evaluate.

• We can simplify that summation by using the fact that log n = o(n^ε) for any ε > 0, and use that to rejigger the sum to make it easier to manipulate.

• With that simplification in place, we basically redo the analysis using the same techniques as before - sums of geometric series, swapping terms in exponents and logs - to arrive at the result.

Hope this helps!