Consider the following three claims — I.(n+k)m = Θ(nm) where k and m are…

Big-O and Big-Theta compare how fast one function grows against another as n → ∞, ignoring constant multipliers and lower-order terms:

• f(n) = Θ(g(n)) when positive constants c1, c2, and n0 exist such that c1·g(n) ≤ f(n) ≤ c2·g(n) for every n ≥ n0 — f and g grow at exactly the same rate.

• f(n) = O(g(n)) when a positive constant c and n0 exist such that f(n) ≤ c·g(n) for every n ≥ n0 — f grows no faster than g, once a constant factor is allowed.

A direct consequence used below: any constant multiple of g(n) is O(g(n)); a polynomial (n+k)m with fixed constants k, m keeps nm as its dominant term, so it is Θ(nm); but if the ratio f(n)/g(n) itself grows without bound as n increases, f(n) is NOT O(g(n)).

1. Claim I: (n+k)m = Θ(nm), for constants k and m. Expanding by the binomial theorem, (n+k)m = nm + m·k·nm-1 + … + km — every term besides the leading one carries a strictly smaller power of n. Since k and m are fixed and don't grow with n, these lower-order terms and constant coefficients never change the asymptotic rate, so (n+k)m grows at exactly the rate of nm. This satisfies the Θ definition — TRUE.

2. Claim II: 2n+1 = O(2n). Since 2n+1 = 2 · 2n, it is exactly 2 times 2n — a constant multiple. Taking c = 2 and n0 = 1 in the O-definition, 2n+1 ≤ c·2n holds for every n ≥ n0. A constant multiplier never changes the O-class, so this holds — TRUE.

3. Claim III: 22n = O(2n). Here 22n = (2n)2 = 4n — not a constant multiple of 2n. The ratio 22n / 2n = 2n itself grows without bound as n increases, so no constant c can satisfy 22n ≤ c·2n for large n. This fails the O-definition — FALSE.

A quick numeric check confirms this: at n = 10, 2n+1 = 2048 is exactly twice 2n = 1024 — a fixed ratio of 2, matching claim II. But 22n = 220 = 1,048,576 against 2n = 1024 gives a ratio of 1024, and this ratio doubles every time n increases by 1 — it can never be capped by a fixed constant, confirming claim III fails.

So claim I and claim II both hold, while claim III does not — the correct combination is I and II.