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
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.