A function has an outer loop that runs n times. Inside it is a second loop that runs log(n) times, doing constant work per iteration. What is the Big-O complexity?
AO(n)
BO(n log n)
CO(n²)
DO(log n)
The outer loop runs n times; for each iteration, the inner loop runs log(n) times doing O(1) work. Total operations: n × log(n) × O(1) = O(n log n). The dominant term combines both loops — you multiply the complexities of nested loops. O(n) would be correct only if the inner loop were constant, and O(n²) only if the inner loop also ran n times.
Question 2 Multiple Choice
Algorithm A is O(n) but performs 1,000 basic operations per element. Algorithm B is O(n log n) but performs 2 operations per element. For n = 100, which algorithm runs faster?
AAlgorithm A, because O(n) is asymptotically superior to O(n log n)
BAlgorithm B, because O(n log n) algorithms always have smaller constants
CAlgorithm B, because 100 × log₂(100) × 2 ≈ 1,328 operations vs. 100 × 1,000 = 100,000
DThey are equivalent for n = 100 since both are polynomial
For n = 100: Algorithm A performs 100 × 1,000 = 100,000 operations; Algorithm B performs 100 × ~6.6 × 2 ≈ 1,320. Algorithm B is ~75× faster despite its worse Big-O class. Big-O tells you about asymptotic behavior as n → ∞, not about small inputs. For n ≈ 10,000,000, Algorithm A would finally overtake B. The key lesson: Big-O rules out choices at scale; for small n, benchmark.
Question 3 True / False
Two algorithms with the same Big-O complexity usually have the same real-world runtime for any given input size.
TTrue
FFalse
Answer: False
Big-O ignores constant factors and lower-order terms. Two O(n log n) algorithms — merge sort and quicksort — can have very different real-world runtimes due to cache behavior, memory access patterns, and implementation constants. An O(n) algorithm with a constant of 10,000 runs slower than an O(n log n) algorithm with a constant of 1 for most practical input sizes. Same Big-O class guarantees only the same asymptotic growth rate.
Question 4 True / False
Big-O notation describes the worst-case upper bound on an algorithm's growth rate, ignoring constant factors and lower-order terms.
TTrue
FFalse
Answer: True
By definition, f(n) = O(g(n)) means there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. This is an upper bound relationship. The 'ignoring constants' part is formalized by the constant c, which absorbs any fixed multiplicative factor. Lower-order terms are dominated by the leading term as n grows. Big-O captures growth rate, not absolute speed.
Question 5 Short Answer
An O(n²) sorting algorithm and an O(n log n) sorting algorithm both solve the same problem. Describe when you might still prefer the O(n²) algorithm, and when you would never use it.
Think about your answer, then reveal below.
Model answer: For very small inputs (n < ~50), an O(n²) algorithm like insertion sort often outperforms O(n log n) algorithms because its constant factors and cache behavior are better — O(n²) with a tiny constant beats O(n log n) with a large one. Many standard libraries use insertion sort for small subarrays inside merge sort or timsort for exactly this reason. However, for large inputs (n in the millions or billions), O(n²) becomes completely infeasible: a trillion operations vs. tens of millions. Big-O tells you what to rule out at scale, not what to always prefer.
The practical wisdom is: use Big-O to eliminate algorithms that will become infeasible as n grows, then benchmark the surviving candidates on your actual data and hardware. The crossover point where O(n log n) becomes faster than O(n²) depends on the specific implementations and constants.