# Asymptotic Notation – Algorithm – Mock Test -2

 Question 1
Consider the following statements

1. If $f(n)=\Theta (g(n))$ and $g(n)=\Theta (h(n))$, then $h(n)=\Theta (f(n))$

2. If $f(n)=O (g(n))$ and $g(n)=O (h(n))$, then $h(n)=\Omega (f(n))$

3. If $f(n)=O (g(n))$ and $g(n)=O (f(n))$, then $f(n)=g(n)$

How many statements are TRUE?
 A 0 B 1 C 2 D 3
Algorithm
Question 1 Explanation:
1 is True. $\Theta$ is transitive.
2 is True. $O$ is transitive, and $h(n)=\Omega (f(n))$ is the same as $f(n)=O (h(n))$
3 is False: $f(n) = n$ and $g(n) = 2n + 1$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
Consider the following functions.

$f(n) = 1$
$g(n) = 2$

Which of the following option is/are TRUE?
[MSQ]
 A $f(n)=\Theta (g(n))$ B $f(n)=\Omega (g(n))$ C $g(n)=\Omega (f(n))$ D $f(n)=O(g(n))$
Algorithm
Question 2 Explanation:
All constants are related to each other by a constant factor, so they have the same order of growth. $f(n)=\Theta (g(n))$, and therefore $f(n)=O (g(n))$ and$f(n)=\Omega (g(n))$ also.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 3
Consider the following functions.

$f(n) = 5n \log n$
$g(n) = n \log (5n)$

Which of the following option is/are TRUE?
[MSQ]
 A $f(n)=\Theta (g(n))$ B $f(n)=\Omega (g(n))$ C $g(n)=\Omega (f(n))$ D $f(n)=O(g(n))$
Algorithm
Question 3 Explanation:
$n \log 5n = n \log 5 + n \log n = \Theta (n \log n)$
Also, $5n \log n = \Theta (n \log n)$

These are the same order of growth, so $f(n)=\Theta (g(n))$, and therefore $f(n)=O (g(n))$ and $f(n)=\Omega (g(n))$ also.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 4
Sorting order of the given functions in increasing order of asymptotic (big-O) complexity is

\begin{aligned} f_1(n)&=n^{\sqrt{n}} \\ f_2(n) &= 2^n \\ f_3(n) &= n^{10} \cdot 2^{\frac{n}{2}} \\ f_4(n) &= \sum_{i=1}^{n}(i+1) \end{aligned}
 A $f_4(n),f_2(n),f_3(n),f_1(n)$ B $f_4(n),f_3(n),f_2(n),f_1(n)$ C $f_4(n),f_1(n),f_2(n),f_3(n)$ D $f_4(n),f_1(n),f_3(n),f_2(n)$
Algorithm
Question 4 Explanation:
The correct ordering of these functions is $f_4(n),f_1(n),f_3(n),f_2(n)$. To see why, we first use the rules of arithmetic series to derive a simpler formula for $f_4(n)$:
\begin{aligned} f_4(n)&=\sum_{i=1}^{n}(i+1) \\ &= \frac{n((n+1)+2)}{2}\\ &= \frac{n(n+3)}{2}\\ &= \Theta (n^2) \end{aligned}
This is clearly asymptotically smaller than $f_1(n)=n^{\sqrt{n}}$. Next, we want to compare $f_1(n), f_2(n)$ and $f_3(n)$. To do so, we transform both $f_1(n)$ and $f_3(n)$ so that they look more like $f_3(n)$:

$f_1(n)=n^{\sqrt{n}}=(2^{\log n})^{\sqrt{n}}=2^{\sqrt{n} \log n}$

$f_3(n)=n^{10}\cdot 2^{n/2}=2^{\log (n^{10})}\cdot 2^{n/2}=2^{n/2+10 \log n}$

The exponent of the 2 in $f_1(n)$ is a function that grows more slowly than linear time; the exponent of the 2 in $f_3(n)$ is a function that grows linearly with $n$. Therefore, $f_1(n)=O(f_3(n))$.
Finally, we wish to compare $f_3(n)$ with $f_2(n)$. Both have a linear function of n in their exponent, so it's tempting to say that they behave the same asymptotically, but they do not. If $c$ is any constant and $g(x)$ is a function, then $2^{cg(x)} = (2^c)^{g(x)}$. Hence, changing the constant of the function in the exponent is the same as changing the base of the exponent, which does affect the asymptotic running time. Hence, $f_3(n)$ is $O(f_2(n))$, but $f_2(n)$ is not $O(f_3(n))$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 5
Sorting order of the given functions in increasing order of asymptotic (big-O) complexity is

\begin{aligned} f_1(n)&=2^{2^{1000000}} \\ f_2(n) &= 2^{100000n}\\ f_3(n) &= \binom{n}{2}\\ f_4(n) &= n\sqrt{n} \end{aligned}
 A $f_1(n),f_4(n),f_2(n),f_3(n)$ B $f_1(n),f_4(n),f_3(n),f_2(n)$ C $f_1(n),f_2(n),f_3(n),f_4(n)$ D $f_1(n),f_3(n),f_2(n),f_4(n)$
Algorithm
Question 5 Explanation:
The correct order of these functions is $f_1(n),f_4(n),f_3(n),f_2(n)$. The variable $n$ never appears in the formula for $f_1(n)$, so despite the multiple exponentials, $f_1(n)$ is constant. Hence, it is asymptotically smaller than $f_4(n)$, which does grow with $n$. We may rewrite the formula for $f_4(n)$ to be$f_4(n)=n\sqrt{n}=n^{1.5}$. The value of $f_3(n) = \binom{n}{2}$ is given by the formula $\frac{n(n-1)}{2}$, which is $\Theta (n^2)$. Hence, $f_4(n)=n^{1.5}=O(n^2)=O(f_3(n))$. Finally, $f_2(n)$ is exponential, while $f_3(n)$ is quadratic, meaning that $f_3(n)$ is $O(f_2(n))$

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 6
Sorting order of the given functions in increasing order of asymptotic (big-O) complexity is

\begin{aligned} f_1(n)&=n^{0.999999} \log n \\ f_2(n) &= 1000000n\\ f_3(n) &= (1.000001)^n\\ f_4(n) &= n^2 \end{aligned}
 A $f_1(n),f_2(n),f_4(n),f_3(n)$ B $f_2(n),f_1(n),f_4(n),f_3(n)$ C $f_1(n),f_2(n),f_3(n),f_4(n)$ D $f_2(n),f_3(n),f_1(n),f_3(n)$
Algorithm
Question 6 Explanation:
The correct order of these functions is $f_1(n),f_2(n),f_4(n),f_3(n)$. To see why $f_1(n)$ grows asymptotically slower than $f_2(n)$, recall that for any $c \gt 0, log n$ is $O(n^c)$. Therefore we have:

\begin{aligned} f_1(n)&=n^{0.999999} \log n \\ &= O(n^{0.999999} \cdot n^{0.000001})\\ &= O(n)=O(f_2(n)) \end{aligned}

The function$f_2(n)$ is linear, while the function $f_4(n)$ is quadratic, so $f_2(n)$ is $O(f_4(n))$.
Finally, we know that $f_3(n)$ is exponential, which grows much faster than quadratic, so $f_4(n)$ is $O(f_3(n))$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST