Given the following equalities : E1: \( n^{K+\in} + n^{K} \lg n = \theta…
2014
Given the following equalities :
E1: \( n^{K+\in} + n^{K} \lg n = \theta (n^{K+\in})\) ) for all fixed \(K\) and \(∈, K \geq 0\) and \(∈ > 0\).
E2 : \( n^{3}2^{n}+6n^{2}3^{n}=O (n^{3}2^{n})\)
Which of the following is true ?
- A.
E1 is correct and E2 is correct.
- B.
E1 is correct and E2 is not correct.
- C.
E1 is not correct and E2 is correct.
- D.
E1 is not correct and E2 is not correct.
Attempted by 228 students.
Show answer & explanation
Correct answer: B
Solution: Determine which equalities hold by comparing growth rates.
First statement (E1): n^{K+ε} + n^{K}·log n = Θ(n^{K+ε}). Reason: Compare the smaller term to n^{K+ε}: (n^{K}·log n)/n^{K+ε} = (log n)/n^{ε}, which tends to 0 as n → ∞ for any fixed ε>0. Thus n^{K}·log n = o(n^{K+ε}), so the sum equals (1+o(1))·n^{K+ε} and is Θ(n^{K+ε}).
Second statement (E2): n^{3}·2^{n} + 6·n^{2}·3^{n} = O(n^{3}·2^{n})? Reason: Examine the second term relative to n^{3}·2^{n}: (6·n^{2}·3^{n})/(n^{3}·2^{n}) = 6·(3/2)^{n} / n. Since (3/2)^{n} grows exponentially, this ratio → ∞, so 6·n^{2}·3^{n} is not bounded by a constant times n^{3}·2^{n}. Therefore the sum is not O(n^{3}·2^{n}).
Conclusion: The first equality is correct and the second equality is not correct.