Solving the recurrence T(n) = T(n/2) + lg n?

Question

I am having some issues on how to solve recurrence relations.

T(n) = T(n/2) + log2(n), T(1) = 1, where n is a power of 2

This is a homework problem, so don't just give me the answer. I was just wondering how to start the problem.

In class we went over the Master theorem. But I don't think that would be the best way to solve this particular relation.

I don't really know how to start the problem... should I just be going

T(n) = T(n/2) + log_base2(n)
T(n/2) = [T(n/4)+log_base2(n/2)]
  T(n) = [T(n/4)+log_base2(n/2)] + log_base2(n) 

And just keep working my way down to get something I can see makes a basic equation?

Answer 1

This recurrence solves to Θ((log n)²). Here are two ways to see this.

Some Substitutions

If you know that n is a perfect power of two (that is, n = 2^k), you can rewrite the recurrence as

T(2^k) = T(2^k-1) + k

Let's define a new recurrence S(k) = T(2^k). Then we get that

S(k) = S(k - 1) + k

If we expand out this recurrence, we get that

S(k) = S(k - 1) + k

= S(k - 2) + (k - 1) + k

= S(k - 3) + (k - 2) + (k - 1) + k

= S(k - 4) + (k - 3) + (k - 2) + (k - 1) + k

...

= S(0) + 1 + 2 + 3 + ... + k

= S(0) + Θ(k²)

Assuming S(0) = 1, then this recurrence solves to Θ(k²).

Since S(k) = T(2^k) = T(n), we get that T(n) = Θ(k²) = Θ(log² n).

Iterating the Recurrence

Another option here is to expand out a few terms of the recurrence and to see if any nice patterns emerge. Here’s what we get:

T(n) = T(n / 2) + lg n

= T(n / 4) + lg (n / 2) + lg n

= T(n / 8) + lg (n / 4) + lg (n / 2) + lg n

...

Eventually, after lg n layers, this recurrence bottoms out and we’re left with this expression:

lg n + lg (n / 2) + lg (n / 4) + ... + lg (n / 2^{lg n)}

Using properties of logarithms, we can rewrite this as

lg n + (lg n - 1) + (lg n - 2) + (lg n - 3) + ... + (lg n - lg n)

Or, written in reverse, this is the sum

0 + 1 + 2 + 3 + ... + lg n

That sum is Gauss’s sum up to lg n, which evaluates to (lg n)(lg n + 1) / 2 = Θ((log n)2).

Hope this helps!