Question 9598 – GATE 2003

Consider the following three claims

I. (n + k)m = Θ(nm), where k and m are constants
II. 2n+1 = O(2n)
III. 22n+1 = O(2n) 

Which of these claims are correct?

Correct Answer: A

I) (n+k)^m = Θ(n^m)
Which is true by considering leading ordered term present in polynomial expression.
II) 2ⁿ⁺¹ = Θ(n^m) → True

2ⁿ×2ⁿ can’t be written as Θ(2ⁿ)
So, this is False.