Register

GATE Overflow Test Series | Data Structures | Test 1 | Question: 18

318 views
3 votes
3 votes
Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs. Let $f(n) = O(g(n))$ and $h(n) = O(g(n)).$ Which of the following is necessarily FALSE?
  1. $f(n) = O(h(n))$
  2. $g(n) = O(f(n))$
  3. $h(n) = \Omega(g(n))$
  4. None of the above are necessarily FALSE
User Avatar

1 Answer

Best answer
6 votes
6 votes
If we use $\leq$ to denote asymptotically less than or equal to, we can write  
 $f(n) = O(g(n))$ and $h(n) = O(g(n))$ as $f \leq g$ and $h \leq g.$
 
 Now, the given choices can be written as
 A. $f \leq h.$ Possible
 
 B. $g \leq f.$ Possible when $f = g.$
 
 C. $h \geq g.$ Possible when $h = g.$
 
 So, none of the given options are necessarily FALSE.
 
 Correct Option: D
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
gatecse asked Aug 9, 2020
261 views
GATE Overflow Test Series | Data Structures | Test 1 | Question: 25
Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs and let $f(n) = o(g(n))$ and $h(n) = \omega(g(n)).$ Which of the following is VALID? $f(n) = \Theta(h(n))$ $g(n) = O(f(n))$ $h(n) = \Omega(g(n))$ $g(n) = \Omega(h(n))$
Let $f(n),g(n)$ and $h(n)$ be the time complexities of three programs and let $f(n) = o(g(n))$ and $h(n) = \omega(g(n)).$ Which of the following is VALID?$f(n) = \Theta(h...
User Avatar
4 votes
4 votes
1 answer
2
gatecse asked Aug 9, 2020
338 views
GATE Overflow Test Series | Data Structures | Test 1 | Question: 27
Pick the correct order of asymptotic growth rate for the following functions. $n^{1/4}, e^n, 3^n, 1.001^n, n^{1000}, n^{\sqrt n}, n!$ $n^{1/4} <n^{\sqrt n}<1.001^n <e^n< 3^n< n!< n^{1000}$ ... $n^{1/4}< n^{1000}<n^{\sqrt n}<1.001^n <e^n< 3^n< n!$
Pick the correct order of asymptotic growth rate for the following functions.$$n^{1/4}, e^n, 3^n, 1.001^n, n^{1000}, n^{\sqrt n}, n!$$$n^{1/4} <n^{\sqrt n}<1.001^n <e^n< ...
User Avatar
1 votes
1 votes
1 answer
3
gatecse asked Aug 9, 2020
294 views
GATE Overflow Test Series | Data Structures | Test 1 | Question: 12
The time complexity of the below code is int isPalindrome ( char * string, int n ) { if (n <= 1) return 1; if (string[0] != string[n-1]) return 0; return isPalindrome(string + 1, n-2); } $\Theta(n)$ $\Theta (n \log n)$ $\Theta(\log n)$ $\Theta(n^2)$
The time complexity of the below code isint isPalindrome ( char * string, int n ) { if (n <= 1) return 1; if (string[0] != string[n-1]) return 0; return isPalindrome(stri...
User Avatar
3 votes
3 votes
1 answer
4
gatecse asked Aug 9, 2020
227 views
GATE Overflow Test Series | Data Structures | Test 1 | Question: 1
The cut vertices in the given graph are E and F A, C and D C, E and F B and C
The cut vertices in the given graph areE and FA, C and DC, E and FB and C
User Avatar
Link Copied!