yeah $O(logn^{1.58})$ to be precise $O(logn^{1.584963})$

Dark Mode

407 views

1 vote

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})$

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})$