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?

templatetypedef · Accepted Answer · 2013-10-06 08:35:00Z

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!

edited Oct 6, 2013 at 8:35

answered Oct 6, 2013 at 7:50

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Jacek Trociński Over a year ago

wouldn't the recurrence be b^k C(n / b^k) + b^k *(n + n/b + ... + n/b^k)

Jacek Trociński Over a year ago

or rather something like this i mean C(n) = b^k * C(n / b^k) + k*n

Collectives™ on Stack Overflow

Complexity of a particular divide and conquer algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related