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?
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?
0 | |
1 | |
2 | |
3 |
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
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]
f(n) = 1
g(n) = 2
Which of the following option is/are TRUE?
[MSQ]
f(n)=\Theta (g(n)) | |
f(n)=\Omega (g(n)) | |
g(n)=\Omega (f(n)) | |
f(n)=O(g(n)) |
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
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]
f(n) = 5n \log n
g(n) = n \log (5n)
Which of the following option is/are TRUE?
[MSQ]
f(n)=\Theta (g(n)) | |
f(n)=\Omega (g(n)) | |
g(n)=\Omega (f(n)) | |
f(n)=O(g(n)) |
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
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}
\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}
f_4(n),f_2(n),f_3(n),f_1(n) | |
f_4(n),f_3(n),f_2(n),f_1(n) | |
f_4(n),f_1(n),f_2(n),f_3(n) | |
f_4(n),f_1(n),f_3(n),f_2(n) |
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
\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}
\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}
f_1(n),f_4(n),f_2(n),f_3(n) | |
f_1(n),f_4(n),f_3(n),f_2(n) | |
f_1(n),f_2(n),f_3(n),f_4(n) | |
f_1(n),f_3(n),f_2(n),f_4(n) |
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
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
There are 5 questions to complete.