Register

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

259 views
1 votes
1 votes
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?
  1. $f(n) = \Theta(h(n))$
  2. $g(n) = O(f(n))$
  3. $h(n) = \Omega(g(n))$
  4. $g(n) = \Omega(h(n))$
User Avatar

2 Answers

2 votes
2 votes
If we use $<$ to denote asymptotically less than, and similarly for the other asymptotic notations, we can write  
 $f(n) = o(g(n))$ and $h(n) = \omega(g(n))$ as $f < g$ and $h > g \implies f < g < h$
 
 Now, the given choices can be written as
 
 A. $f = h.$ Invalid
 
 B. $g \leq f.$ Invalid
 
 C. $h \geq g.$ Valid
 
 D. $g \geq h.$ Invalid
 
 So, correct option: C
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
1 answer
1
gatecse asked Aug 9, 2020
318 views
GATE Overflow Test Series | Data Structures | Test 1 | Question: 18
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? $f(n) = O(h(n))$ $g(n) = O(f(n))$ $h(n) = \Omega(g(n))$ None of the above are necessarily FALSE
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?$f(n) = O(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!