retagged by
19,262 views
34 votes
34 votes

For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is

  1. $\Theta (\log_a  \log _b  n)$   
  2. $\Theta (\log_{ab} n$)
  3. $\Theta (\log_{b}  \log_{a}  \: n$)
  4. $\Theta (\log_{2} \log_{2} n$)
retagged by

4 Answers

Best answer
70 votes
70 votes
$T(n) = \left\{\begin{matrix}
T\left(n^{1/a}\right) + 1 & ;\text{when}\; n \neq b \\
 1 &  ;\text{when}\; n = b
\end{matrix}\right.$

Now, $T(n) = T\left(n^{1/a}\right) + 1$

   $\qquad \quad = T\left(n^{1/a^{2}}\right) + 1 + 1 \quad \left[\because T\left(n^{1/a}\right) = T\left(n^{1/a^{2}}\right) + 1\right]$

 $\qquad \quad = T\left(n^{1/a^{3}}\right) + 1 + 1  + 1 \quad \left[\because T\left(n^{1/a^{2}}\right) = T\left(n^{1/a^{3}}\right) + 1\right]$

After $k$ iterations,  $T(n) = T\left(n^{1/a^{k}}\right) + k$

When $n^{1/a^{k}} = b,i.e., \dfrac{1}{a^{k}} \log n = \log b$

$\implies a^{k} = \dfrac{\log n}{\log b}$

$\implies k = \log_{a} \log _{b} n$

$[\because a \& b $ are $\omega (1),$ so $a\&b$ are some function of $n$ and not constant. So $a\&b$ can’t be replaced with $2]$

So, option D is rejected.

Now, $T(n) = T\left(n^{1/a^{k}}\right) + k$

$\quad\qquad = T(b) + \log_{a} \log_{b} n$

$\quad\qquad = 1 + \log_{a} \log_{b} n$

$\quad\qquad =  \Theta \left(\log_{a} \log_{b} n \right)$

So, the correct answer is A.
edited by
5 votes
5 votes

$T(n) = T(n^{\frac{1}{a}}) + 1$

let a = 2 for simplicity,

$T(n) = T(n^{\frac{1}{2}}) + 1$

$T(n) = T(n^{\frac{1}{2^2}}) + 1 + 1 = T(n^{\frac{1}{2^2}}) + 2 $

$T(n) = T(n^{\frac{1}{2^3}}) + 1 + 1 + 1 = T(n^{\frac{1}{2^3}}) + 3 $

 

after k iterations, it is like

$T(n) = T(n^{\frac{1}{2^k}}) + k $  --- (1)

 

for base condition : T(b) = 1

$n^{\frac{1}{2^k}} = b $

==> $ 2^k = log_b^n$

==> $ k = log_2^{log_b^n}$ 

Substitute this value in (1)

 

$T(n) = T(b) + k  =  O(1) + log_2^{log_b^n} $

 

replace 2 by 'a'

$T(n) = T(b) + k  =  O( log_a^{log_b^n} ) $

3 votes
3 votes

$T(n) = T(n^{\frac{1}{a}}) + 1$

 

(Change of variables method)

Put $n = 2^m$

$m = log_2n$


$T(2^m) = T(2^{\frac{m}{a}}) + 1$

Let $S(m) = T(2^m)$, which gives $S(\frac{m}{a}) = T(2^{\frac{m}{a}})$

 

$S(m) = S(\frac{m}{a}) + 1$

since $T(b)=1$ and we assumed $S(m) = T(2^m)$ so if $2^m$ = $b$

$T(2^m) = 1$ so $m=log_2b$

$S(log_2b) = 1$

$S(m) = S(\frac{m}{a^2}) + 1+1$

$S(m) = S(\frac{m}{a^2}) + 2$

$S(m) = S(\frac{m}{a^3}) +1 + 2$

$S(m) = S(\frac{m}{a^3}) + 3$

.

.

.

$S(m) = S(\frac{m}{a^k}) + k$

---------------------------------------------------------------------------------------------------------------

as $S(log_2b) = 1 ,\frac{m}{a^k} = log_2b$ to make$  S(\frac{m}{a^k})$  equal to 1

$m = log_2n$

$\frac{log_2n}{a^k} = log_2b$

$\frac{log_2n}{log_2b} =a^k$

make base b by base change rule

$\frac{log_bn}{log_bb} =a^k$

${log_bn} =a^k$

apply $log_a$ on both sides

$k=log_alog_bn$


$S(m) = S(\frac{m}{a^k}) + k$

$S(m) = 1+ log_a log_bn$

$ = Θ(log_a log_bn) $

0 votes
0 votes
$T(n) = T(n^{\frac{1}{a}}) + 1$

let a = 2 for simplicity,

$T(n) = T(n^{\frac{1}{2}}) + 1$

i.e.

$T(n)=T(\sqrt{n})+1$

          $ =T(2^{\frac{m}{2}})+1$    $n=2^{m}$ , $m=log n$

 $S(m)=S(m/2)+1$

           $ =(m^{0})=1$

           $=O(m^{0}log m)$

Now put the value $n=a^{m}$ , $m=log_{a} n$

So, complexity will be  $=O(log log_{a} n )$

So, answer should be C)
edited by
Answer:

Related questions

8 votes
8 votes
4 answers
4
Arjun asked Feb 12, 2020
9,633 views
Consider a graph $G = (V,E)$, where $V = \{v_1,v_2, \dots ,v_{100}\}$, $E = \{(v_i,v_j) \mid 1\leq i < j \leq 100\}$, and weight of the edge $(v_i,v_j)$ is $\mid i – j ...