Questions: Complexity Classes and Asymptotic Analysis

Question 1

An O(n²) algorithm runs a problem of size n = 1,000 in 1 second. Approximately how long will it take for n = 1,000,000?

• A. About 1,000 seconds (~17 minutes)
• B. About 1,000,000 seconds (~11 days)
• C. About 2 seconds, since n only grew by a constant factor
• D. About 1,000,000,000 seconds (~31 years)

Answer: (B)

When n grows by a factor of 1,000, an O(n²) algorithm's runtime grows by 1,000² = 1,000,000. So 1 second becomes 1,000,000 seconds — about 11.5 days. This illustrates why complexity classes represent qualitatively different scalability, not just faster or slower: an O(n²) algorithm that works at n = 10,000 becomes completely impractical at n = 1,000,000.

Question 2

Binary search runs in O(log n) time. Approximately how many comparisons does it need to search a sorted list of 1 billion items?

• A. About 500 million — it checks half the list on average
• B. About 1 million — it processes a fraction of the list
• C. About 30 — each comparison halves the remaining search space
• D. About 1,000 — it scans a small linear subset

Answer: (C)

log₂(1,000,000,000) ≈ 30. Each comparison in binary search discards half the remaining candidates, so after 30 steps you've narrowed a billion items to one. This is the power of logarithmic time: any time you can discard half the problem at each step, the number of steps grows only as the logarithm of the input size, making it nearly constant compared to linear or quadratic approaches.

Question 3

An O(n log n) sorting algorithm and an O(n²) sorting algorithm are essentially equivalent for large inputs — both are polynomial, so the performance gap is minor.

• T. True
• F. False

Answer: False

While both are technically polynomial, the performance gap is enormous at scale. For n = 1,000,000, an O(n²) algorithm does around a trillion operations; O(n log n) does about 20 million — a factor of roughly 50,000 difference. The classes are qualitatively different in practice. This is precisely why efficient sorting algorithms like merge sort (O(n log n)) replaced naive ones like bubble sort (O(n²)) for real-world use.

Question 4

Exponential-time algorithms (O(2^n)) are considered computationally intractable for large inputs because they grow faster than any polynomial function of n.

• T. True
• F. False

Answer: True

For n = 50, O(2^n) is over a quadrillion operations. For n = 100, it exceeds the number of atoms in the observable universe. No polynomial grows this fast. This is why the distinction between polynomial time and superpolynomial time (including exponential and factorial) is the central dividing line in theoretical computer science — it separates problems that are feasible from those that are not, regardless of hardware improvements.

Question 5

What is the fundamental distinction between polynomial-time complexity classes and superpolynomial ones, and why does this distinction matter for practical algorithm design?

Model answer: Polynomial-time algorithms (O(n^k) for fixed k) remain feasible as input size grows because their runtime grows proportionally to a power of n. Superpolynomial algorithms (O(2^n), O(n!)) grow so fast that even small increases in n make them completely impractical — doubling n doubles a linear algorithm's time, but doubles an exponential algorithm's runtime squared. The distinction matters because it separates problems we can actually solve from problems that are computationally intractable regardless of hardware.

This dividing line — polynomial vs. superpolynomial — motivates the entire P vs. NP question in theoretical computer science. Problems in P (solvable in polynomial time) can be handled practically; problems whose best known algorithms are exponential may require approximations, heuristics, or special-case solutions. No amount of Moore's Law improvement overcomes exponential growth.