12,791 views

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

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

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

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

a and b are lower bound by w(1) , hence they are some function of n

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

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

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

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

by

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

ω 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