in Algorithms retagged ago by
12,791 views
19 votes
19 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$)
in Algorithms retagged ago by
by
12.8k views

4 Comments

@Bhaskar_Saini

I think Master’s theorem cannot be applied here because ‘a’ and ‘b’ are not constants. It is mentioned in the question that they are ω(1) and small omega notation is a lower bound which is not tight. So, this tells us that ‘a’ and ‘b’ are not constants.

2
2

@harshschauhan Thank you so much for Help.

0
0
Can we apply master's if a and b is given Θ(1)?
0
0

4 Answers

59 votes
59 votes
Best answer
$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^{2}}\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

4 Comments

“a and  b are w(1) so a and b are some function of n” i am not getting this line?

any one explain please.
1
1
a and b are lower bound by w(1) , hence they are some function of n
3
3

There’s a slight typo while calculating T(1/n^(a^2)) in 4th line of solution. It must be  T(1/n^(a^3))+1+1+1 

0
0
4 votes
4 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} ) $

4 Comments

@d3ba

I think, Whatever @aditya059 is saying, is correct. Only issue is : when $b=n$ then $T(n)= \Theta(0)$ which is meaningless. I think in question, they should have to mention that all functions for b are allowed except 'n' i.e $b \neq n.$ $T(b)=1$ is not meaningless. I was wrong. Here, $T(n) = 1+ log_alog_b n $. So, $T(b)= 1+ log_alog_bb$. Now, whatever the function we take for $b$, $T(b)$ will always be $1$.

0
0
Some IIT professor might ask to prove the same question for interview :)
1
1

@Arjun Sir

Can it be challenged or not?

0
0
1 vote
1 vote

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

by
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

4 Comments

@aditya059

what w(1), actually means? Is it not mean constant? Otherwise it would be O(a) or something else. right?

0
0
ω is called little omega. Here ω(1) means strictly greater than constant.

Ω(1) means greater or equal to 1, i.e. , constant or some function of n

but ω(1) means asymptotically greater than 1, i.e., some function of n other than constant
0
0
0
0
Answer:

Related questions