TIFR CSE 2024 | Part B | Question: 4

Question

Consider functions $f$ and $g$ from the set of positive real numbers to itself, recursively defined as follows.
\[
\begin{array}{rrl}
\forall n \leq 1 & f(n), g(n) & =1, \\
\forall n>1 & f(n) & =3 f(n / 3)+n^{2}, \\
\forall n>1 & g(n) & =n^{2 / 3} g\left(n^{1 / 3}\right)+n .
\end{array}
\]

Which of the following options is correct about their asymptotic behaviour?

• A. $f(n)=\Theta\left(n^{2}\right)$ and $g(n)=\Theta(n \log \log n) \checkmark$
• B. $f(n)=\Theta\left(n^{2}\right)$ and $g(n)=\Theta(n \log n)$
• C. $f(n)=\Theta\left(n^{2} \log n\right)$ and $g(n)=\Theta(n \log \log \log n)$
• D. $f(n)=\Theta\left(n^{2} \log n\right)$ and $g(n)=\Theta(n \log \log n)$
• E. $f(n)=\Theta\left(n^{2} \log n\right)$ and $g(n)=\Theta(n \log n)$

   

Answer 1

first part-

$f(n)=3 f(n/3) +n^{2}$ 

Use Master Theorem –

$T(n)=aT(n/b) + F (n)$

Compare $n^{log{_{b}}^{a}}$    and  $  F (n)$

$n^{log{_{3}}^{3}}$     $n^{2}$  

$\Rightarrow$   $n$     $n^{2}$    in both of these  $n^{2}$   is polynomially greater. So TC  $\Theta (n^{2})$ 

 

Second part-

$g(n)= n^{2/3} g(n^{1/3})+n$ 

Divide  $n$  both the side

 $g(n)/n= n^{2/3} g(n^{1/3})/n+n/n$

 $g(n)/n=  g(n^{1/3})/n^{1/3}+1$

Let’s Assume This to Be $ s(n) $

 $s(n)=  s(n^{1/3})+1$

Now Put $n= 2^{m} $

 $s(2^{m})=  s(2^{m/3})+1$

Take $ Log$ of inner Part

$s(m)=  s(m/3)+1$

Use Master’s Theorem 

$m^{log{_{3}}^{1}}$   $1$  So TC will be    $\Theta (logm)$ 

And We Know   $n= 2^{m} $

  $m=  log n $

$\Theta (log log n)$ 

And This Ans is Of $ S(n) $ 

We know  $g(n)/n $ =  $ (log log n)$ 

So $g(n)$  =   $\Theta (nloglogn)$