retagged by
305 views

1 Answer

Best answer
2 votes
2 votes
$T\left ( n \right )=\sqrt{n}\, *\, T\left ( \sqrt{n} \right )\: +100n$

Let $n= 2^{k}$

$\Rightarrow T\left ( 2^{k} \right )= \left ( 2^{k} \right )^{1/2}\, *\, T\left ( \left ( 2^{k} \right )^{1/2}\right )+100*2^{k}$

$\Rightarrow T\left ( 2^{k} \right )= 2^{k/2}\, * \, T\left ( 2^{k/2} \right )+100*2^{k}$

$\Rightarrow $ dividing both side by $2^{k}$$\Rightarrow T\left ( 2^{k} \right )/2^{k}=T\left ( 2^{k/2} \right )/2^{k/2}+100$

Let $T\left ( 2^{k} \right )/2^{k}=Y\left ( k \right )$

$\Rightarrow Y\left ( k \right )=Y\left ( k/2 \right )+100$

Using Master theorem $a=1,b=2,k=0,p=0\Rightarrow a= b^{k}\Rightarrow case 2\Rightarrow Y\left ( k \right )=\Theta \left ( \log_{2}k\right )$

$\Rightarrow we\, have \, Y\left ( k \right )=\log_{2}k\, and \, we \, know \, that T\left ( 2^{k} \right )/2^{k}=Y\left ( k \right )$

$T\left ( 2^{k} \right )=2^{k}*\, Y\left ( k \right )\Rightarrow 2^{k}*\log_{2}k\Rightarrow n*\log \log n$

$\Rightarrow T\left (n\right )= \Theta \left ( n*\log \log n \right )$
selected by

Related questions

1.2k
views
1 answers
0 votes
Shreya2002 asked Oct 27, 2022
1,202 views
How to solve this recurrence relationT(n)= T(0.09n) + T(0.91n) + cnwhere c is constant and T(1)=1options are-
940
views
2 answers
1 votes
srestha asked May 10, 2019
940 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
905
views
1 answers
0 votes
9.3k
views
2 answers
2 votes
pradeepchaudhary asked Jul 14, 2018
9,328 views
Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by— T(n)= T(n-1) + 1/n, if n>1 = 1, otherwise.The order of the algorithm is—(a) log n(c) n^2(b) n(d) n*n