retagged by
299 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

0 votes
0 votes
1 answer
1
Shreya2002 asked Oct 27, 2022
1,169 views
How to solve this recurrence relationT(n)= T(0.09n) + T(0.91n) + cnwhere c is constant and T(1)=1options are-
1 votes
1 votes
2 answers
2
srestha asked May 10, 2019
925 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
0 votes
0 votes
1 answer
3
2 votes
2 votes
2 answers
4
pradeepchaudhary asked Jul 14, 2018
9,275 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�...