Self-Assessment Quiz: Algorithms and Complexity

Twenty questions to check your understanding of asymptotic analysis. Answer before opening the key. Aim for 16+.

Question 1

The Big-O definition "$f(n) = O(g(n))$" requires that there exist constants $c > 0$ and $n_0$ such that:

A) $f(n) = c \cdot g(n)$ for all $n$ B) $f(n) \le c \cdot g(n)$ for all $n \ge n_0$ C) $f(n) \ge c \cdot g(n)$ for all $n \ge n_0$ D) $f(n) \le c \cdot g(n)$ for some single value of $n$

Question 2

To prove a Big-O membership from the definition, you must:

A) measure the running time on several inputs B) exhibit witnesses $c$ and $n_0$ and verify the inequality for all $n \ge n_0$ C) show the witnesses are unique D) compute the limit $\lim_{n\to\infty} f(n)/g(n)$

Question 3

Which statement is the tight characterization of the growth of $5n^2 + 3n + 100$?

A) $O(n^3)$ B) $\Omega(n)$ C) $\Theta(n^2)$ D) $O(n^2)$ only

Question 4

In the RAM model, the cost of the single line new_list = old_list + [x] on a list of length $n$ is:

A) $\Theta(1)$ B) $\Theta(\log n)$ C) $\Theta(n)$ D) $\Theta(n^2)$

Question 5

A loop that halves the size of its working range on every pass, starting from $n$, runs in:

A) $\Theta(\log n)$ B) $\Theta(n)$ C) $\Theta(n \log n)$ D) $\Theta(\sqrt{n})$

Question 6

The input size used when analyzing an algorithm that operates on an integer $N$ is normally:

A) $N$ B) $\log_2 N$ (its number of bits) C) $\sqrt{N}$ D) $N^2$

Question 7

Order from slowest- to fastest-growing: $n^2,\ \log n,\ 2^n,\ n \log n,\ n,\ n!$.

A) $\log n \prec n \prec n\log n \prec n^2 \prec 2^n \prec n!$ B) $n \prec \log n \prec n\log n \prec n^2 \prec n! \prec 2^n$ C) $\log n \prec n \prec n^2 \prec n\log n \prec 2^n \prec n!$ D) $\log n \prec n \prec n\log n \prec n^2 \prec n! \prec 2^n$

Question 8

"Polynomial time" means the running time is:

A) $\Theta(n^2)$ exactly B) $O(n^k)$ for some constant $k$ C) $O(n \log n)$ D) $\Omega(c^n)$ for some $c > 1$

Question 9

A 1000× faster computer lets an $O(2^n)$ algorithm handle an input larger by about:

A) 1000× B) $\sqrt{1000} \approx 32$ more elements C) about 10 more elements D) no change at all

Question 10

Which pair of nested loops is not $\Theta(n^2)$?

A) for i in range(n): for j in range(n): work() B) for i in range(n): for j in range(i+1, n): work() C) for i in range(n): for j in range(7): work() D) for i in range(n): for j in range(i): work()

Question 11

The sum rule says that running phase $A$ ($\Theta(n \log n)$) then phase $B$ ($\Theta(n^2)$) gives a total of:

A) $\Theta(n^3 \log n)$ B) $\Theta(n^2 \log n)$ C) $\Theta(n^2)$ D) $\Theta(n \log n)$

Question 12

"Worst case" and "Big-O" are:

A) two names for the same thing B) independent axes: one names which input, the other names a bound shape C) mutually exclusive D) only meaningful together

Question 13

The best-case running time of binary search on a sorted list of $n$ elements is:

A) $\Theta(1)$ B) $\Theta(\log n)$ C) $\Theta(n)$ D) $\Theta(n \log n)$

Question 14

The lower bound "finding the max of $n$ distinct numbers needs $\ge n - 1$ comparisons" is proved by:

A) running the best known algorithm B) counting that each comparison creates at most one new "loser," and $n-1$ losers are required C) induction on the list values D) the sum rule

Question 15

Which base do we write inside $O(\log n)$, and why?

A) base 2, because computers are binary B) base 10, by convention C) none — all log bases differ by a constant factor, so they share one $\Theta$-class D) base $e$, because it is the natural log

Question 16 (True/False, justify)

True or false: $3n + 7 = O(n^2)$. Justify in one sentence, and say whether the bound is tight.

Question 17 (True/False, justify)

True or false: If $f(n) = \Theta(g(n))$ then $g(n) = \Theta(f(n))$. Justify in one sentence by appeal to the definition.

Question 18 (True/False, justify)

True or false: An algorithm whose worst-case time is $\Theta(n^2)$ can still have a best-case time of $\Theta(1)$. Justify with a one-line example.

Question 19 (Short answer)

State the three growth-class "doubling fingerprints" the Project Checkpoint estimator reports: when you double $n$, what ratio of operation counts indicates linear, quadratic, and cubic growth?

Question 20 (Short answer)

In one sentence each, explain (a) why we count operations instead of measuring seconds, and (b) why an $\Omega$ lower bound on a problem is a stronger statement than an $O$ bound on a single algorithm.

Answer Key

Topics to review by question