Multiple choice

Consider the following three claims I. (n + k)m = O (nm) where k and m are constants II. 2n+1 = O(2n) III. 22n+1 = O(2n)

Which of these claims are correct?

  1. I and II

  2. I and III

  3. II and III

  4. I, II, and III
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

(1) $(n + k)^m$ if we exapnd it. It is $(n^m + .....)$ During tight bound $\theta (n^m)$ correct (2) $ 2^{n+1} = 2.2^n \Rightarrow O(2.2^n) \Rightarrow O(2^n) \quad correct $

$ 2^{2n+1} = 2.2^2n \Rightarrow O(2.2^2n) $ $ O(2^{2^n}) \neq O(2^n) \quad incorrect $

Keep practicing — related questions