in Algorithms retagged by
19,229 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$)
in Algorithms retagged by
by
19.2k views

4 Comments

in this question what is the meaning of the statement 

For parameters a and b, both of which are ω(1)

 

1
1

@m1racle  it means that,  the rate of growth of a and b is ω(1). 
ω(1)  means  rate of growth is strictly greater than constant.  
Constants have  rate of growth as Θ(1).

1
1

Here in the question it’s given a and b are ω(1). That means our parameters, a and b have their rate of growth not equal to Θ(1) and cannot be taken as constants.

So this question can be solved in 2 ways :

  1. Changing Variable Method – Ans we are getting : $T(n) =\Theta ( log_{2} log_{2}(n))$    [Please follow the comment above by @d3ba]
  2. By Iteration Method –  Ans we are getting : $T(n) =\Theta ( log_{a} log_{b}(n))$          [Please follow the ans tagged as best by @aditya059]

So best answer for this question would be option A.

0
0

4 Answers

70 votes
70 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^{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

4 Comments

how did a^k=logn/logb was solved ??? pls explain me someone
0
0

@atul kaintyura please check the previous comment left by @RasMalai if your doubt still remains then your can ping me.

0
0
Just because \(a\) and \(b\) are \(\omega(1)\) need not mean \(a\) and \(b\) are necessarily some function(s) of \(n\), right? They aren’t constants is what we can infer. Can anything more be said than that?
0
0
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} ) $

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 :)
2
2

@Arjun Sir

Can it be challenged or not?

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

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

ω 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
1
1
1
1
Please read cormen (CLRS book’s) Growth of Functions Chapter, thoroughly. you will get to know everything clearly in detail.
0
0
Answer:

Related questions