CODEWITHSUNDEEP
algorithmtime-complexityasymptotic-complexity
Billie
Billie

Reputation: 9146

How to calculate the upper bound time complexity (`"big O`") of a recursive function?

Suppose I have a recursive function T, and I want to calculate the upper bound timer complexity of this function.

T(1) = 3

T(n) = 3T(n/3) + 3.

How can I find the upper bound of the time complexity of T(n)?

Upvotes: 2

Views: 2215

Answers (2)

pgpb.padilla
pgpb.padilla

Reputation: 2418

Use the master theorem case formula where a=3, b=3, c=0.

solution

I highly recommend the MIT lectures on Algorithms. You can learn more about the Master theorem in lecture 2

Upvotes: 3

xbob.ym
xbob.ym

Reputation: 521

assume that, n = 3^k

F(0) = 3

F(k) = 3 * F(k-1) + 3

 = 3^2 * F(k-2) + 3^2 + 3

 = ...

 = 3^k * F(0) + 3^k + 3^(k-1) + ... + 3

 = 3^(k+1) + 3^k + ... + 3^2 + 3

 = [3^(k+2) - 3] / 2

T(n = 3^k) = F(k) = (9 * n - 3) / 2 = O(n)

Upvotes: 0

Related Questions