Consider the recurrence that naturally arises in some divide-and-conquer algorithms: T(1)= 1, T(n) = 4T(n/2) +...

 

Transcribed Image Text:

Consider the recurrence that naturally arises in some divide-and-conquer algorithms: T(1)= 1, T(n) = 4T(n/2) + n for n > 1 [a] Explain what the initial condition and the various parts of this recurrence mean in the context of the analysis of algorithms. [b] Use the Master Theorem to determine the order of magnitude of T(n). [c] Using the methods of our course, derive a closed-form formula for T(n). [d] For the case n = 2, test your formula for T(n) against the original recurrence. Consider the recurrence that naturally arises in some divide-and-conquer algorithms: T(1)= 1, T(n) = 4T(n/2) + n for n > 1 [a] Explain what the initial condition and the various parts of this recurrence mean in the context of the analysis of algorithms. [b] Use the Master Theorem to determine the order of magnitude of T(n). [c] Using the methods of our course, derive a closed-form formula for T(n). [d] For the case n = 2, test your formula for T(n) against the original recurrence.