GATE CSE 2020 | Question: 2

Question

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

• A. $\Theta (\log_a  \log _b  n)$   
• B. $\Theta (\log_{ab} n$)
• C. $\Theta (\log_{b}  \log_{a}  \: n$)
• D. $\Theta (\log_{2} \log_{2} n$)

Comments

Why is the answer not  $\theta(log_2log_2(n))$ ?

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

 

(Change of variables method)

Put $n = 2^k$

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

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

 

Hence, $S(k) = S(\frac{k}{a}) + 1$

Master's Theorem can be applied here.

$f(k) = 1$ and $g(k) = k^{log_a(1)} = k^0 = 1$

 

Therefore, $f(k) = \theta(g(k))$ which gives $S(k) = \theta(f(k)\times log_2(k)) = \theta(log_2(k))$

 

$S(k) = \theta(log_2(k))$

$T(2^k) = \theta(log_2(k))$

$T(n) = \theta(log_2log_2(n)$)

---

@d3ba

what about this question?

---

can’t we use master method for this question????
Please Help!!

---

@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.

---

@harshschauhan Thank you so much for Help.

---

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

---

in this question what is the meaning of the statement 

For parameters a and b, both of which are ω(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).

---

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] (which is not exactly correct as here a & b rate of growth is not θ(1))
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.

---

https://youtu.be/cjO6uo8rBbE?list=PLIPZ2_p3RNHgz_uIqO3iGfZETeqNAyVUH&t=14218 solution

 

---

easy trick given T(b)=1 substitute only option a satisfies

Answer 1

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

Comments

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

---

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?

---

its a logarithmic form:

$a^k = X \implies k = \log_a X$

Answer 2

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

Comments

Change of variable doesn't makes things easier in this case , better we do without changing the variable as base case is not for the constant value

Answer 3

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

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

---

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

---

@Arjun Sir

Can it be challenged or not?

Answer 4

Answer 5

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

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

---

chk this page last example here https://www.geeksforgeeks.org/analysis-of-algorithems-little-o-and-little-omega-notations/

---

Please read cormen (CLRS book’s) Growth of Functions Chapter, thoroughly. you will get to know everything clearly in detail.