PA of Algorithms Q34

0. Consider the following three claims
l. (n + k)^m = Θ(n^m), where k and m are constants
2. 2^{n + 1} = O(2ⁿ)
3. 2^{2n + 1} = O(2ⁿ)
Which of these claims are correct?

Answer
Comment
Array

Option : A
Explanation :
Note:- In devotion place change first point by
1. (n+k)^m = O(n^m), where k and m are constants.
1. (n+k)m ≅ O (nm) because k & m are constant
then growth rate of both the function is same.
2. 2ⁿ⁺¹ ⇒ 2.2ⁿ, Here 2 is constant
So function is 2ⁿ. Statement is true.
3. 2²ⁿ⁺¹ ⇒ 2.2²ⁿ ⇒ 2.4ⁿ
So 4ⁿ > 2ⁿ then 2²ⁿ⁺¹ ≠ O(2ⁿ).

Forgot your password?

I agree with the Terms.