edited by
650 views
1 votes
1 votes
What will be the solution of the following recurrence?

$$T(n)=3T\sqrt{n}+\log(n)$$
edited by

2 Answers

Best answer
2 votes
2 votes
$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

Related questions

1 votes
1 votes
0 answers
1
srestha asked May 19, 2019
594 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
0 votes
0 votes
1 answer
2
jatin khachane 1 asked Jan 2, 2019
340 views
Let T(n) be a function defined by the recurrence T(n)=2T(n/2)+√n for n≥2 andT(1)=1Can someone please explain solution of this using back substitution
0 votes
0 votes
2 answers
3
Verma Ashish asked Sep 19, 2018
710 views
How to solve the given recurrence relation using master's theorem?T(n)=T(${n^{1/2}}$)+n
0 votes
0 votes
1 answer
4
eyeamgj asked Jun 24, 2018
397 views
consider the following c program A(n){if(n<=1)return(n2 +n+1)elsereturn(5A(n/2)+3A(n/2)+MA(n))}where MA(n) has complexity O(n2).1.what is the recurrence relation for valu...