in Algorithms edited by
407 views
1 vote
1 vote
What will be the solution of the following recurrence?

$$T(n)=3T\sqrt{n}+\log(n)$$
in Algorithms edited by
407 views

4 Comments

edited by
yeah $O(logn^{1.58})$ to be precise  $O(logn^{1.584963})$
0
0
Yeah it is ,thanks

You did it by master theorem
0
0
right :), check out my answer below
0
0

2 Answers

2 votes
2 votes
Best answer
$T(n) = 3T \sqrt{n} + logn$

Now, assuming,

$q = logn \\ Or, n = 2^q$

$∴ T(n) = T(2^q) \\ = 3T \sqrt{2^q} + q \\ = 3T. (2^\left(q/2 \right)  )+ q$

Now, taking

$X(q ) = T(2^q) \\ ∴ X(q) = 3.X \left (\dfrac{q}{2} \right ) + q $

Now, applying Master Method,

According to Master Method,

Recurrence relation should be in this form,

$$aT \left ( \dfrac{n}{b} \right ) + f(n) , \text{where, } a \geq 1 \hspace{0.1cm} \& \hspace{0.1cm} b>1$$

& we have the equation as : $X(q) = 3.X.(\dfrac{q}{2})+q$

Here, $a = 3, b = 2$

According to master theorem

$\text{If } f(n) = \Theta(n^c), \text{ where }, c < \log_b a, \text{ then, } T(n ) = \Theta (n^ {\log_b a})$

& if $a > b^c$ & $c<\log_b a$, then it will be satisfy $Case-1)$ of Master method

∴ $X(q) = \Theta(q^{\log_2 3 }) \\  \qquad = \Theta(q^{1.58}) $

Now, putting back the value of $q$ which is $\log n$

∴ $T(n) = \Theta(\log n ^{1.58})$
edited by

2 Comments

'c' is missing in first equation?
0
0
is it ok now ?
0
0
1 vote
1 vote

check this

2 Comments

Thanks Mam for the effort
0
0
i was happy to help :)
0
0

Related questions