Calculate number of step and time complexity for equation:
T(n) = 2 T(n/4) + 5 where n > 1, T (1) = 1
What is the Big O Notation?
Asked
Active
Viewed 30 times
-2
-
1This isn't a homework-answering service. I don't think StackOverflow wants to be filled with millions of algorithms with people asking what their Big O is. It doesn't help the community. – Smartcat Mar 03 '18 at 17:44
-
Google *Master theorem*. – meowgoesthedog Mar 03 '18 at 19:25
1 Answers
0
Your second step is not correct. You have to replace the T(n/4) term and not just add to the end of your equation. That way you get:
T(n) = 2T(n/4) + 5
= 2(2T(n/16)+5)+5 = 2²T(n/16) + (2¹+1)*5
= 2²(2T(n/64)+5) + (2¹+1)*5 = 2³T(n/64) + (2³+1)*5
= 2³(2T(n/256)+5) + (2³+1)*5 = 2⁴T(n/256) + (2⁶+1)*5
AstridNeu
- 31
- 3