CODEWITHSUNDEEP
algorithmdata-structuresrecurrence
Riadiani
Riadiani

Reputation: 85

Expanding Recurrence Relation and Finding Closed Form

I have a snippet of algorithm and must find the worst-case recurrence and find its closed form. So far I have the worst-case recurrence:

T(n)= 2T(n/4) + C for n > 1.

I tried expanding it, and I have this form currently:

T(n) = 2kT(n/4k) + Ck

with k = log4(n) or k = (log2(n))/2.

I have T(1) = 1000.

I am at a loss on what to do next, or how to find its closed form exactly. I still cannot see a pattern in the algorithm or my expansion of T(n). Any insight would be great, thank you.

Upvotes: 0

Views: 481

Answers (1)

Brainless
Brainless

Reputation: 1758

What you can get is a closed formula when n = 4^k:

T(4^k) = 2^k x 10^3 + C + 2C + ... + 2^(k-1)C
       = 2^k x 10^3 + (2^k - 1)C

Where the last eqaulity comes from the geometric series formula.

For all other n, I think the best you can do is to apply the master theorem

Your equation falls in case 1 of the theorem (you have a = 2, b = 4, c = 0). Therefore:

log_b(a) = 1 / 2

and

T(n) = O(sqrt(n))

I'm not sure if it admits an unique closed form.

Upvotes: 2

Related Questions