How can i solve $T(n) = T(n/3) + T(n/4) +5n$ using iteration method to find time complexity of the requrrence?
Asked
Active
Viewed 113 times
0
-
Why do you believe you can solve this relation with the iteration method? I'm certain there's no simple closed form here... – Steven Stadnicki Jun 14 '20 at 16:02
-
You can solve the relation using whatever method you want to use, i wrote that because i know one method now. – ShooterLens Aim Jun 14 '20 at 16:06
-
What is "time complexity of the recurrence"? And why do you think there is a solution? $n/3$ may not be an integer? – markvs Jun 14 '20 at 16:21
-
@JCAA It is a result of our bad educational system, unfortunately i have to deal with this. My teacher says the solution is O(n) but i don't know the way of solve that. – ShooterLens Aim Jun 14 '20 at 16:23
-
It's easy to see that $T(n)=12,n$ is a solution. But so is $T(n)=12,n+c,n^\alpha,$ where $\alpha$ is the solution of $3^{-\alpha}+4^{-\alpha}=1$ (it's slightly bigger than $1/2$), for any value of $c$. – Jun 14 '20 at 18:11