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

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

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

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

---

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

Answer 2

$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

Hence, option A is correct.

---

both of which are $\omega(1)?$ What's the significance of this?

---

@Arjun Sir this means that we can't take a and b as constant.otherwise d will become correct ans

---

If $(A)$ is correct then $(C)$ and $(D)$ MUST also be correct.

Here, by back-substitution, your answer is option $(A)$ i.e  $T(n) \in \Theta(log_alog_bn)$

Now, we can re-write it as $T(n ) \in$ $\Theta(log_a(\frac{log_2 n}{\log_2b}))$ [$\because log_ba = \frac{log_ca}{log_cb}$]

$\Theta(log_a(\frac{log_2 n}{\log_2b}))$

$\Theta(log_a(log_2 n)- log_a(log_2b))$

$\Theta\left ( \frac{log_2(log_2 n)}{log_2a}- log_a(log_2b) \right )$ , $a>1$

$\Theta(log_2log_2n)$ which is option $(D)$

Now, consider option $(C)$ i.e $\Theta(log_blog_an)$

Now, re-write it as :

$\Theta(log_b(\frac{log_2 n}{\log_2a}))$

$\Theta(log_b(log_2 n)- log_b(log_2a))$

$\Theta\left ( \frac{log_2(log_2 n)}{log_2b}- log_b(log_2a) \right )$ , $b>1$

$\Theta(log_2log_2n)$ which is option $(D)$

we can go forward or backward like this and can change one option to another option.

Here, $T(n)$ is recursive 'function' of 'n'. So, 'n' should vary and 'a' & 'b' should be constant.

---

@Shaik Masthan

sir, please correct me if I am wrong somewhere.

---

@ankitgupta.1729

a and b are w(1), which means they are not constant.they are some function of n.So how can u replace them with 2? for eg: a and b can even be n.

Suppose a and b are order of n then option A will give correct result as f(n) will become constant. but D will still give O(log log n).Correct me if i am wrong

---

<deleted>

---

@d3ba

Therefore, S(k) ≤ S(k / 2 ^ kx) + 1

Apply Master's Theorem now,

This step is wrong as u cant apply Master theorem in above case. You must remember when Master theorem can be applied. Actually a and b must be constant to apply Master theorem. but in your case b = 2 ^ kx

which is not constant

---

Yes you're right. My bad.

---

@aditya059

"for eg: a and b can even be n."

then option (A) becomes $\Theta(0)$. right ? what does it mean ?

and also what is the meaning of base condition i.e. T(f(n)) = 1... Here, left side is like function of function and right side is 1 (straight line) which is a constant. Then,  How, both can be equal ? (Assuming b=f(n) is not a constant function)

I agree with you that a and b can be function of n as $n$,$n^2$, $nlgn$ etc. but I want to know why a and b can't be constant function or simply constant.

Definition of small-omega says :

$f(n) \in \omega(g(n))$ :

$\omega(g(n)) = \{f(n) :$ for any positive constant $c>0$ there exists a constant $n_0$ such that $0 \leq cg(n) < f(n)$ for all $n \geq 0$  $\}$

Now, here, $a > c*1$ for all $c>0$. So, if you give me any $c$ , I can find $a$ by just adding $1$.

---

@ankitgupta.1729

Refer this for your doubt

https://www.geeksforgeeks.org/analysis-of-algorithems-little-o-and-little-omega-notations/

Actually little omega means strictly greater, i.e, asymptotically bigger and not tight bound.

Time complexity will not become θ(0) as f(n) i.e. min 1 unit of work is always done.It will become order of constant.

1 more thing it is asymptotic notation and not simple maths that by adding 1 we get a larger function

 

---

@aditya059

Have I not used stritctly greater than sign ?

Question is not related to "time complexity" because here no algorithm is given whose running time generally we write as recurrence. Here, we have to write the solution of given recurrence asymptotically.

---

@aditya059

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

w(1) is nothing but  $lim\frac{2n+1}{1}$ which means it is divided by 1 or some constant, which results tends to $\infty$

right??

---

@ankitgupta.1729

I know that u have used strictly greater sign.I was just answering your query for this line

" I agree with you that a and b can be function of n as n,n2, nlgn etc. but I want to know why a and b can't be constant function or simply constant. "

the definition of little omega can be rewritten as f(n) = ω(g(n)) if lim f(n)/g(n) = infinity

That is why , a, b = ω(1) means lim a/1 = inf. if u take a as constant then lim a/1 will become contant and will not satisfy definition of little omega

@srestha

Refer this for your doubt.Hope this will clear your doubt

                                                                                                         

---

@aditya059

No, it means lower limit must not any effect on upper limit, and it almost like constant..

---

Since the answer was striked off, does this mean this answer (and even the question) is wrong ? I agree with @ankitgupta.1729 that if $b$ is treated as a function of $n$, then $T(b) = 1$ becomes meaningless.

---

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

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

Answer 4

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