in Algorithms retagged by
440 views
2 votes
2 votes
T(n) = 2T(n/4) + log n

How to solve above recurrence?
in Algorithms retagged by
by
440 views

2 Answers

3 votes
3 votes

Ans . O(√n)

By Masters Theorems Case 1

a > $b^k$

edited by

2 Comments

Isn''t there any other method? I mean I know it's the master theorem (the greater version of it) but if I don't want to memorize it then how can I solve?
0
0
By Back Substitution Method
1
1
1 vote
1 vote

We know that any positive polynomial function grows faster than any polylogarithmic function. 

Or, if $c > 0$ , $\log n = O(n^c)$

if we put upper bound of $\log n$ in the given recurrence relation it becomes :

$T(n) = {\color{Blue} 2T\left ( \frac{n}{4} \right ) } + O(n^c)$

Complexity of the first term in the right hand side is = $O(\sqrt n)$.

If we choose a small value for c such as 0.001 then, $\sqrt n > n^{0.001}$

=> $T(n) = O(\sqrt n)$

edited by
by

Related questions