GATE 2008
March 14, 2025GATE 2008
March 14, 2025GATE 2008
| Question 39 |
Consider the following functions:
-
f (n) = 2n
g(n) = n!
h (n) = nlogn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
| f(n) = O(g(n)); g(n) = O(h(n))
| |
| f(n) = Ω(g(n)); g(n) = O(h(n)) | |
| g(n) = O(f(n)); h(n) = O(f(n)) | |
| h(n) = O(f(n)); g(n) = Ω(f(n))
|
Question 39 Explanation:
When we want to find asymptotically bigger/smaller functions, we have to follow basically 2 steps:
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
Correct Answer: D
Question 39 Explanation:
When we want to find asymptotically bigger/smaller functions, we have to follow basically 2 steps:
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.