Skip to main content
1 of 2
user16666
  • 81
  • 1
  • 1
  • 2

To prove the recurrence by substitution method T(n) = 7T(n/2) + n^2

I have done the proof until the point when T(n) <= cn^log7

But when it comes to finding the value of constant c. I am getting stuck.

The given recurrence relation is enter image description here

Since we already calculated the solution above which is . Inductive Step :

Now we have to prove that T(n) <= c n^log7 where c is a positive constant. If we consider that the solution holds good for n/2 then we can prove that it works for n also: T(n/2) <= c(n/2)^ log7 Substituting these values in the recurrence relation :

T(n) <= 7c/(2)^log7 * (n)^log7 + n^2

 <= cn^log7 , since 7/(2)^log7  is a constant so it can be ignored and cn^log7 >> n^2 for large value of n
                                 
 <= cn^log7 assuming c is a constant >=1

. Finally to find constant c

(7/(2)^log7) * cn^log7 + n^2 <= cn^log7

So i am not able to find appropriate c for which the condition holds true.

user16666
  • 81
  • 1
  • 1
  • 2