Big-O Notation — Data Structures 练习题

Grades 11–12 / College 困难难度 10 道题

Big-O notation describes how an algorithm's runtime or space grows as input size n increases. It focuses on worst-case asymptotic behavior and ignores constants and lower-order terms.

Common classes from fastest to slowest: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential.

Examples: array index access O(1); binary search O(log n); linear scan O(n); nested loops over n O(n²); recursive Fibonacci without memo O(2ⁿ). Choose data structures to match operation needs.

练习的技能

Classifying algorithms by Big-O
Comparing growth rates
Analyzing loops and nested loops
Connecting structure choice to complexity

姓名： 日期： 课时：

练习题：Big-O Notation

说明： 仔细解答每一道题。清晰地展示所有解题过程。在指定位置或按指示在另一张纸上写出最终答案。

1.Determine the Big-O complexity of the following function: $f(n) = 3n^3 + 2n^2 + 5n + 1$ . Provide a brief justification.

Big-O Notation — 练习题（续）

2.Sort the following functions in increasing order of asymptotic growth rate (from slowest to fastest): $n \log n$ , $2^n$ , $n^2$ , $\log n$ , $n!$ , $n$ , $n^{0.5}$ . Write your final ordering.

Big-O Notation — 练习题（续）

3.
Consider the following code fragment:
```
for i = 1 to n:
    for j = 1 to i:
        print(i + j)
```
What is the Big-O time complexity of this code? Explain your reasoning.

Big-O Notation — 练习题（续）

4.True or False: $2^{n+1} = O(2^n)$ . Justify your answer.

Big-O Notation — 练习题（续）

5.Multiple Choice: Which of the following is equivalent to $\Theta(n^2)$ ?
1. A. $O(n^2)$ and $\Omega(n^2)$
2. B. $O(n^2)$ only
3. C. $\Omega(n^2)$ only
4. D. Neither $O(n^2)$ nor $\Omega(n^2)$

Big-O Notation — 练习题（续）

6.Determine the Big-O complexity of the recurrence $T(n) = 2T(n/2) + n$ . Assume $T(1) = 1$ . Show your work using the Master Theorem or iteration method.
7.Given $f(n) = n^2 \log n$ and $g(n) = n^2 \sqrt{n}$ , determine whether $f(n) = O(g(n))$ , $f(n) = \Omega(g(n))$ , or $f(n) = \Theta(g(n))$ . Justify your answer.

Big-O Notation — 练习题（续）

8.Multiple Choice: What is the Big-O complexity of the following function? \[ f(n) = \sum_{i=1}^{n} i^2 \]
1. A. $O(n)$
2. B. $O(n^2)$
3. C. $O(n^3)$
4. D. $O(\log n)$

Big-O Notation — 练习题（续）

9.Prove or disprove: $n^3 + 100n^2 = \Omega(n^3)$ . Provide a formal proof using the definition of Big-Omega.

Big-O Notation — 练习题（续）

10.Consider the algorithm that finds the maximum element in an unsorted array of size $n$ . What is the tightest asymptotic bound for its worst-case time complexity? Explain why.

参考答案

1.

The highest-order term is $3n^3$ , so the function grows as $n^3$ . All lower-order terms are dominated.

最终答案： $O(n^3)$
2.

最终答案： $\log n$ , $n^{0.5}$ , $n$ , $n \log n$ , $n^2$ , $2^n$ , $n!$
3.

The outer loop runs $n$ times, and the inner loop runs an average of $n/2$ times, giving approximately $n^2/2$ operations, which is $O(n^2)$ .

最终答案： $O(n^2)$
4.

$2^{n+1} = 2 \cdot 2^n$ , so $2^{n+1} \leq c \cdot 2^n$ for $c = 2$ and all $n \geq 0$ . Thus $2^{n+1} = O(2^n)$ .

最终答案： True
5.

By definition, $\Theta(n^2)$ means the function is both $O(n^2)$ and $\Omega(n^2)$ .

最终答案： (A) $O(n^2)$ and $\Omega(n^2)$

参考答案（续）

6.

Using the Master Theorem with $a=2$ , $b=2$ , $f(n)=n$ , we have $\log_b a = 1$ , and $f(n) = n = \Theta(n^1)$ , so case 2 applies: $T(n) = \Theta(n \log n)$ .

最终答案： $O(n \log n)$
7.

Compare: $n^2 \log n$ vs $n^2 \sqrt{n} = n^{2.5}$ . Since $\log n$ grows slower than $n^{0.5}$ , $f(n)$ is asymptotically smaller, so $f(n) = O(g(n))$ but not $\Omega(g(n))$ .

最终答案： $f(n) = O(g(n))$
8.

The sum $\sum_{i=1}^{n} i^2 = n(n+1)(2n+1)/6$ , which is $\Theta(n^3)$ .

最终答案： (C) $O(n^3)$
9.

We need constants $c > 0$ and $n_0$ such that $n^3 + 100n^2 \geq c n^3$ for all $n \geq n_0$ . Choose $c = 1$ and $n_0 = 1$ : $n^3 + 100n^2 \geq n^3$ for all $n \geq 1$ . Thus $n^3 + 100n^2 = \Omega(n^3)$ .

最终答案： True
10.

The algorithm must examine each element once to find the maximum, requiring $n-1$ comparisons in the worst case, which is $\Theta(n)$ .

最终答案： $O(n)$

下载 PDF

需要避免的常见错误

Confusing best case with Big-O (usually worst case)
Calling O(2n) different from O(n) — constants drop
Ignoring hidden loops in string operations
Assuming recursion is always O(2ⁿ)

生成您自己的练习表

想要一套难度自选的 big-o notation 新题？使用 WorksheetSmith 在几秒内编译一份可打印的自定义 PDF。

生成自定义 Big-O Notation 练习表

最后更新：2026

Big-O Notation — Data Structures 练习题

练习的技能

参考答案

需要避免的常见错误

生成您自己的练习表

相关练习表