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

Click Here to Practice ALL Previous MOCK TEST FREE
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)) andf(n)=\Omega (g(n)) also.

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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
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 bef_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

Click Here to Practice ALL Previous MOCK TEST FREE
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 functionf_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

Click Here to Practice ALL Previous MOCK TEST FREE
There are 6 questions to complete.

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.