Complexity of a particular divide and conquer algorithm

Question

An algorithm decomposes (divides) a problem of size n into b sub-problems each of size n/b where b is an integer. The cost of decomposition is n, and C(1)=1. Show, using repeated substitution, that for all values of 2≥b, the complexity of the algorithm is O(n lg n).

This is what I use for my initial equation C(n) = C(n/b) + n and after k-steps of substituting I get C(n) = C(n/b^k) + n [summation(from i=0 to k-1) of (1/b)^i]

k = log(base b) n

I'm not sure I'm getting all of this right because when I finish doing this i don't get n lgn, anybody can help me figure out what to do?

Answer 1

I think your recurrence is wrong. Since there are b separate subproblems of size n/b, there should be a coefficient of b in front of the C(n / b) term. The recurrence should be

C(1) = 1

C(n) = b C(n/b) +O(n).

Using the Master Theorem, this solves to O(n log n). Another way to see this is that after expanding the recurrence k times, we get

C(n) = b^k C(n / b^k) + kn

This terminates when k = log_b n. Plugging in that value of k and simplifying yields a value that is O(n log n).

Hope this helps!