confused about a pair of recursion relations

Question

thanks in advance for your help in figuring this out. I'm taking an algorithms class and I'm stuck on something. According to the professor, the following holds true where C(1)=1 and n is a power of 2:

C(n) = 2 * C(n/2) + n resolves to C(n) = n * lg(n) + n

C(n) = 2 * C(n/2) + lg(n) resolves to C(n) = 3 * n - lg(n) - 2

The first one I completely grok. As I understand the form, what's stated is that C(n) resolves to two sub-problems, each of which requires n/2 work to solve, and an additional n amount of work to split and merge everything. As such, for every division of the problem, the constant 2 is increased by a factor of ^k (where k is the number of splits), the 2 in n/2 is also increased by a factor of ^k for much the same reason, and the last n is multiplied by a factor of k because each split creates a multiple of k extra work.

My confusion stems from the second relation. Given that the first and second relations are almost identical, why isn't the result of the second something like nlgn+(lgn^2)?

Answer 1

The general result is the Master Theorem

But in this specific case, you can work out the math for a power of 2:

C(2^k) 
= 2 * C(2^(k-1)) + lg(2^k) 
= 4 * C(2^(k-2)) + lg(2^k) + 2 * lg(2^(k-1))
= ... repeat ...
= 2^k * C(1) + sum (from i=1 to k) 2^(k-i) * lg 2^i
= 2^k + lg(2) * sum (from i=1 to k) 2^(i) * i
= 2^k - 2 + 2^k+1 - k
= 3 * 2^k - k - 2 
= 3 * n - lg(n) - 2