Q37.Marks: +2.0UGC NET Paper 2: Computer Science 18th June 2024 Shift 1 (Cancelled)
A least integer n such that f(x) is O(xn) for each of the following functions. Arrange follow according to the value of n in increasing order :
A. f(x) = 3x3 + (log x)4
B. f(x) = (x5 + x2 + 1)/(x3 + 1)
C. f(x) = (x3 + x2 + 1)/(x2 + 1)
D. f(x) = (x2 + 5 log x)/(x2 + 1)
Choose the correct answer from the options given below :
1.D, C, A, B
2.D, C, B, A✓ Correct
3.B, C, A, D
4.B, A, C, D
Solution
The correct answer is D, C, B, A
Key Points
To determine the least integer ( n ) such that f(x) is \(O(x^n)\) for each function, we need to analyze the growth of each function as \(x \to \infty\).
Let's examine each function:
A. \(f(x) = 3x^3 + (\log x)^4\)
The term \(3x^3\) dominates as \(x \to \infty\) since \((\log x)^4 \) grows much slower than \(3x^3\). Therefore, f(x) is dominated by \(3x^3\) and f(x) is \(O(x^3)\).
n = 3
B. \(f(x) = \frac{x^5 + x^2 + 1}{x^3 + 1}\)
To find the dominant term, we note that as \(x \to \infty\):
x5 in the numerator dominates x2 + 1.
x3 in the denominator dominates 1.
Thus, \(f(x) \sim \frac{x^5}{x^3} = x^2\)
So, f(x) is O(x2).
n = 2
C. \(f(x) = \frac{x^3 + x^2 + 1}{x^2 + 1}\)
Similarly, as \( x \to \infty\):
x3 in the numerator dominates x2 + 1.
x2 in the denominator dominates 1.
Thus, \( f(x) \sim \frac{x^3}{x^2} = x\)
So, f(x) is O(x).
n = 1
D. \(f(x) = \frac{x^2 + 5 \log x}{x^2 + 1}\)
As \(x \to \infty\):
x2 in the numerator dominates \(5 \log x\).
x2 in the denominator dominates 1.
Thus, \(f(x) \sim \frac{x^2}{x^2} = 1\)
So, f(x) is O(1).
n = 0
Now, we arrange the functions in increasing order of ( n ):
( D: n = 0 )
( C: n = 1 )
( B: n = 2 )
( A: n = 3 )
Thus, the correct answer is: D, C, B, A
The integer ( n ) ordering is correct for the first option according to the dominance factors determined.