GATE CS 2003 Q20 — Asymptotic Worst Case Time and Space Complexity

We analyze each claim individually using the definitions of asymptotic notations:

1. Claim I: $(n+k)^m = \Theta(n^m)$ where $k, m$ are constants.
   Expanding using the binomial theorem, the leading term is $n^m$. Since $k$ and $m$ are constants, all other terms are of lower order. Thus, $(n+k)^m = \Theta(n^m)$. This claim is correct.
2. Claim II: $2^{n+1} = O(2^n)$.
   We can rewrite $2^{n+1}$ as $2 \cdot 2^n$. Since $2 \cdot 2^n \le c \cdot 2^n$ holds for any constant $c \ge 2$, we have $2^{n+1} = O(2^n)$. This claim is correct.
3. Claim III: $2^{2n+1} = O(2^n)$.
   We can rewrite $2^{2n+1}$ as $2 \cdot 4^n$. There is no constant $c$ such that $2 \cdot 4^n \le c \cdot 2^n$ for all sufficiently large $n$, because the ratio $\frac{2 \cdot 4^n}{2^n} = 2 \cdot 2^n$ grows infinitely. This claim is incorrect.

Therefore, only claims I and II are correct.