CODEWITHSUNDEEP
algorithmrecursiontime-complexity
om1999
om1999

Reputation: 127

calculate the complexity of an algorithm using Back Substitution

I have the function :

int ps (int n) 
{ if (n == 1) return 1; 
 else return (Extra(n) + Ps (n/4) + Ps (n/4)); }

Extra(n) is O(n)

I have tried to find T(n) of this function which is T(n)=T(n)+2 T(n/4) and I have calculated the complexity using the master theorem it is O(n) but I don't know how to find the complexity of it using back substitution

Upvotes: 0

Views: 1275

Answers (1)

OmG
OmG

Reputation: 18838

First, you are wrong in terms of complexity. You didn't mention Extra(n) in writing the time complexity. So, T(n) = 2 T(n/4) + n. Now, I think the new recurrent complexity term is easy to solve by substitution:

T(n) = 2T(n/4) + n = 2 (2 T(n/8) + n/4) + n = 2^2 T(n/8) + n/2 + n =
2^2 (2 T(n/16) + n/8) + n/2 + n = 2^3 T(n/16) + n/4 + n/2 + n

Now, by mathematical induction, if we suppose n = 2^k, you can find that:

T(n) = n + n/2 + n/4 + n/8 + ... + n/2^k = n (1 + 1/2 + 1/4 + ... + 1/2^k) <= 2n

The last part of the above analysis comes from the being geometric series of the sum with factor 1/2. Hence, T(n) is in Theta(n) and O(n).

Upvotes: 1

Related Questions