GATE CSE 2022 | Question: 1

Question

Which one of the following statements is $\text{TRUE}$ for all positive functions $f(n)?$

• A. $f(n^{2}) = \theta (f(n)^{2}),$ when $f(n)$ is a polynomial
• B. $f(n^{2}) = o (f(n)^{2})$
• C. $f(n^{2}) = O (f(n)^{2}),$ when $f(n)$ is an exponential function
• D. $f(n^{2}) = \Omega (f(n)^{2})$

Comments

$ \text{Polynomial Function Definition(Asymptotically) :} f(n) = n^r,   $ for some $r \geq 0$ (Since the options are interested in the asymptotic comparison of growth of positive functions)

$\color{red}{\text{Proof of correctness of Option A : }} $

Since $f(n)$ is polynomial, So, assume $f(n) = n^r, \text{ for some } r \geq 0 $

So, $f(n^2) = (n^2)^r = n^{2r} $

Also, $f(n)^2 = (n^r)^2 = n^{2r} $ 

Hence, $f(n^2) = \Theta(f(n)^2) , \text{ where } f(n) \text{ is a polynomial function }$

For more details, read this comment :

https://gateoverflow.in/371935/Gate-cse-2022-question-1?show=372047#c372047

---

why option d is wrong can anyone please explain it to me?

---

@ZaheenAfzal take f(n) = logn

Answer 1

Answer A.

$f(n^2) \text{ versus }f(n)^2 \color{red}{\text{ asymptomatically }}$

1.Take $f(n) = logn$. $ \text{      }f(n^2) = 2logn$ and $f(n)^2  = logn logn$.
Here $\color{green}{f(n^2) < f(n)^2 }\\$

2.Take $f(n) = e^n$. $ \text{      }f(n^2) = e^{n^2}$ and $f(n)^2  = e^n e^n = e^{2n}$.
Here $\color{blue}{f(n^2) > f(n)^2 } $.
You can verify this by taking $log$ both sides in $e^{n^2}$ and $e^{2n}\\$.

3.Take $f(n)$ as polynomial say, $f(n) = n^3$.  $f(n^2) = {(n^2)^3 = n^6}$ and $f(n)^2 = {(n^3)^2 = n^6}$.
Here  $\mathbf{\color{violet}{f(n^2) = f(n)^2 }}\\ $ 

Option A.
$f(n^2)=Θ(f(n)^2)$ which is $f(n^2) =f(n)^2$.when f(n) is a polynomial function.
This is TRUE because of point 3.

Option B.
$f(n^2)=o(f(n)^2)$ which is $f(n^2) < f(n)^2$.
Obviously this is false beacuse it depends on $f(n)$.

Option C.
$f(n^2)=O(f(n)^2)$ which is $f(n^2) \leq f(n)^2$. when $f(n)$ is an exponential function.
This is false because of point 2 mentioned above.

Option D
$f(n^2)=Ω(f(n)^2)$ which is $f(n^2) \geq f(n)^2$.
Obviously this is false beacuse it depends on $f(n)$.

Comments

for Option (1)

f(n)=Θ g(n)

it means there are positive constants c1, c2  such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)

in your case f(n)= 2logn

g(n) = logn logn

it means 

0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)

=>    c1 logn logn ≤ 2logn ≤ c2 logn logn

=>   c1 logn ≤ 2  ≤ c2 logn

=>   c1  ≤ 2 / (logn)  ≤ c2

here c1 and c2 is fix  but n is variable so this statement is wrong

I think none of these are correct

---

From Algorithm Analysis point of view :

We must understand the definition of functions that are commonly used while analyzing algorithms.

Let ($n$ = size of input, $c$ = some constants $>0$; $b$ = some constant $>=0$)

$f(n) = c, $  $\text{(constant function)}$
$f(n) = log_cn, $  $\text{(logarithmic function)}$ 
$f(n) = n, $  $\text{(linear function)}$ 

$f(n) = n^2, $  $\text{(quadratic function)}$ 

$f(n) = n^b, $  $\text{(polynomial function)}$ 

$f(n) = c^n, $  $\text{(exponential function)}$

$f(n) = n!, $  $\text{(factorial function)}$ 

$f(n) = (log_cn)^b, $  $\text{(logarithmic function)}$ 

All these functions can also be in multiple of some constant $k >0.$

$\color{red}{\text{Proof of correctness of Option A : }} $

Since $f(n)$ is polynomial, So, assume $f(n) = n^r, \text{ for some } r \geq 0 $

So, $f(n^2) = (n^2)^r = n^{2r} $

Also, $f(n)^2 = (n^r)^2 = n^{2r} $ 

Hence, $f(n^2) = \Theta(f(n)^2) , \text{ where } f(n) \text{ is a polynomial function }$

Extra Notes :

NOTE : logarithmic function grow slower than any non-constant polynomial function.

i.e. $f(n)= constant *n^b$  grows faster than $g(n)=log_cn$ for all b,c>0.

We can say that $f(n)>g(n)$ as $n$ approaches infinity.

If we take some limits, we find :

and

https://kconrad.math.uconn.edu/blurbs/analysis/growth.pdf

https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time

https://math.stackexchange.com/questions/1663818/does-the-logarithm-function-grow-slower-than-any-polynomial

https://mathwiki.cs.ut.ee/asymptotics/05_polynomial_complexity

https://www.shmoop.com/functions-graphs-limits/comparing-polynomial-log.html

---

@ssgvns In option $(A)$, $f(n)$ needs to be polynomial. $\log n$ or $2\log n$ are not polynomial functions.

You can prove the statement of option $(A)$ with the help of limits.

If $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} \neq 0, \infty$ then $f(n) = \Theta(g(n))$ provided limit exists.

So, consider a real polynomial of degree $m$ as $f(n) = a_0 + a_1n + a_2n^2+ a_3n^3 + a_4n^4+...+a_mn^m$

$f(n^2) = a_0 + a_1n^2 + a_2n^4 + a_3n^6 + a_4n^8 + … + a_m n^{2m}$

Now, $\lim_{n \rightarrow \infty} \left(\frac{(f(n))^2}{f(n^2)} \right) = \lim_{n \rightarrow \infty} \frac{(a_0 + a_1n + a_2n^2+ a_3n^3 + a_4n^4+...+a_mn^m)^2}{a_0 + a_1n^2 + a_2n^4 + a_3n^6 + a_4n^8 + … + a_m n^{2m}} $

$= \lim_{n \rightarrow \infty} \frac{n^2\left(\frac{a_0}{n} + a_1 + a_2n+ a_3n^2 + a_4n^3+...+a_mn^{m-1}\right)^2}{n^2\left(\frac{a_0}{n^2} + a_1 + a_2n^2 + a_3n^4 + a_4n^6 + … + a_m n^{2m-2}\right)}$

$=\lim_{n \rightarrow \infty} \frac{(a_1 + a_2n + a_3n^2+ a_4n^3 +...+a_mn^{m-1})^2}{a_1 + a_2n^2 + a_3n^4 + a_4n^6 +  … + a_m n^{2m-2}} $

$= \lim_{n \rightarrow \infty} \frac{n^2\left(\frac{a_1}{n} + a_2 + a_3n+ a_4n^2 + ...+a_mn^{m-2}\right)^2}{n^2\left(\frac{a_1}{n^2} + a_2 + a_3n^2 + a_4n^4 +… + a_m n^{2m-4}\right)}$

$=\lim_{n \rightarrow \infty} \frac{(a_2 + a_3n + a_4n^2+ ...+a_mn^{m-2})^2}{a_2 + a_3n^2 + a_4n^4 + … + a_m n^{2m-4}} $

$= \lim_{n \rightarrow \infty} \frac{n^2\left(\frac{a_2}{n} + a_3 + a_4n+ ...+a_mn^{m-3}\right)^2}{n^2\left(\frac{a_2}{n^2} + a_3 + a_4n^2 + … + a_m n^{2m-6}\right)}$

$=\lim_{n \rightarrow \infty} \frac{(a_3 + a_4n +...+a_mn^{m-3})^2}{a_3 + a_4n^2 + … + a_m n^{2m-6}} $

If we do like this and see the patterm, at the end, we’ll get

$= \lim_{n \rightarrow \infty} \frac{(a_{m-1}+a_m n^{m-(m-1)})^2}{a_{m-1}+a_m n^{2m-(2(m-1))}}$

$= \lim_{n \rightarrow \infty} \frac{(a_{m-1}+a_m n)^2}{a_{m-1}+a_m n^2}$

$= \lim_{n \rightarrow \infty} \frac{n^2\left(\frac{a_{m-1}}{n} + a_m\right)^2}{n^2 \left(\frac{a_{m-1}}{n^2} + a_m\right)}$

$= \frac{a_m^2}{a_m} = a_m$

Since, $a_m \neq 0, \infty$, It means $f(n)^2 = \Theta(f(n^2))$ or $f(n^2) = \Theta (f(n)^2)$ 

(You can also see that $(f(n))^2$ is a polynomial in $n$ with highest exponent as $2m$, so, $f(n)^2 = \Theta(n^{2m})$ and $f(n^2)$ is also a polynomial in $n$ with highest exponent as $2m$ because $n$ is replaced with $n^2$, so $f(n^2) = \Theta(n^{2m})$ and so, $f(n^2) = \Theta(f(n)^2)$)