Select the function that is O(2n).

Question

BlackTom AI · Accepted Answer

Big-O compares asymptotic growth rates: f(n) is O(g(n)) if there exist constants c > 0 and n0 such that for all n ≥ n0, |f(n)| ≤ c·|g(n)|. Here g(n) = 2n (a linear function), so we ask which candidate functions grow no faster than a constant multiple of 2n.

1) 3n:
- Compute inequality: 3n ≤ c·(2n) for n ≥ 1.
- Divide both sides by n (positive for n ≥ 1): 3 ≤ 2c ⇒ c ≥ 3/2.
- Choose c = 3/2 and n0 = 1. Then for all n ≥ 1, 3n ≤ (3/2)·2n = 3n (equality holds).
- Therefore 3n is O(2n). This satisfies the Big-O definition exactly.

2) n!:
- Factorial grows faster than any polynomial or linear function. Consider the ratio n! / (2n). As n increases, this ratio → ∞, so no constant c can bound n! by c·2n for all large n.
- Example: for n = 10, 10! = 3,628,800 whereas 2n = 20; clearly 10! far exceeds any fixed constant times 20 for sufficiently large n. Thus n! is not O(2n).

3) n^2 (written as n2):
- Consider ratio (n^2) / (2n) = n/2. This ratio grows without bound as n → ∞, so no fixed c exists to make n^2 ≤ c·2n for all large n. Hence n^2 is not O(2n).

4) n log n + 4n:
- Divide by 2n: (n log n + 4n)/(2n) = (log n)/2 + 2. The term (log n)/2 grows unbounded as n → ∞, so the whole expression cannot be bounded by a constant. Therefore n log n + 4n is not O(2n).

Why the correct answer is correct: 3n is linear, differing from 2n only by a constant factor (3/2), so it satisfies the formal Big-O condition with explicit c and n0. All other options grow asymptotically faster than linear and cannot be bounded by a constant multiple of 2n.

Conclusion: The correct choice is 3n, matching the provided answer.

Select the function that is O(2n).单项选择题

类似问题

Which class of functions grows slowest, among those given as choices?

What is the simplified Big-O notation for 3 ⋅ 𝑁 3 + 𝑂 ( 2 𝑁 2 ) ?

Which of the following would have a exponential Big O run-time complexity?

Select the function that is O(2n).

Gf_4 If the running time of an algorithm A is always O(f(n)), then the worst-case running time of A is also O(f(n)).

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单