Big O Notation Quiz
Questions: 16 · 10 minutes
1. A recursive binary search passes only array indices and creates one recursive call at each level. What is its auxiliary call-stack space complexity?
O(n), because the original array contains n elements.
O(1), because each individual stack frame has constant size.
O(log n), because one frame is added at each level while the search range is repeatedly halved.
O(n log n), because the array size is combined with the recursion depth.
2. An algorithm performs 4n² + 3n + 20 basic operations. What is its tight asymptotic running time?
Quadratic time, because the n² term dominates as n grows.
Linear time, because lower-order terms and constants are removed.
Logarithmic time, because only the number of input-size digits matters.
Cubic time, because the expression contains three separate terms.
3. If an algorithm takes Θ(n²) time, approximately how does its work change when n is doubled for large n?
It becomes about four times as large.
It becomes about twice as large.
It becomes about eight times as large.
It remains approximately unchanged.
4. An outer loop runs with i from 1 through n. For each i, an inner loop runs i times. What is the tight total time complexity?
Quadratic time, because 1 + 2 + ... + n grows proportionally to n².
Linear time, because the outer loop has exactly n iterations.
Linearithmic time, because the inner-loop lengths vary between 1 and n.
Logarithmic time, because each successive iteration changes the loop bound.
5. Using an adjacency-list representation, breadth-first search visits each reachable vertex and examines each relevant edge a bounded number of times. In terms of vertices V and edges E, what is its time complexity?
O(log V), because traversal repeatedly divides the set of vertices.
O(V) for every graph, regardless of how many edges it contains.
O(V + E), accounting for both visited vertices and examined edges.
O(VE), because each vertex requires a scan of every edge.
6. A variable starts at 1 and is doubled after each iteration until it reaches or exceeds n. How many iterations occur asymptotically?
O(log n) iterations.
O(n) iterations.
O(1) iterations.
O(n log n) iterations.
7. A divide-and-conquer algorithm splits a problem into two half-sized subproblems and performs linear additional work at each level. Its recurrence is T(n) = 2T(n/2) + Θ(n). What is the tight solution?
Logarithmic overall time, counting only the number of recursive levels.
Linear overall time, assuming all work across the recursion occurs once.
Quadratic overall time, multiplying the two subproblems by the input size.
Linearithmic overall time, because each of logarithmically many levels does linear total work.
8. What does O(1) time mean most accurately?
The operation always takes exactly one machine instruction.
The operation is guaranteed to be faster than every O(log n) operation.
The operation uses one unit of memory for every input item.
Its running time is bounded independently of the input size.
9. A hash table uses separate chaining, and all n stored keys collide into the same bucket. What is the worst-case lookup time in this situation?
O(1), because hash table lookup is always constant time.
O(log n), because the bucket size is repeatedly halved.
O(n log n), because hashing and chain traversal multiply.
O(n), because the lookup may scan the entire chain.
10. Which notation states that g(n) is both an asymptotic upper bound and an asymptotic lower bound for f(n)?
Big O, which by itself expresses an asymptotic upper bound.
Big Theta, which expresses matching asymptotic upper and lower bounds.
Big Omega, which by itself expresses an asymptotic lower bound.
Little o, which expresses a strictly smaller asymptotic growth rate.
11. How does Θ(n log n) compare with Θ(n²) as n becomes sufficiently large?
Θ(n log n) eventually grows faster because it contains two factors.
Their asymptotic order depends on the base of the logarithm.
They have the same asymptotic growth rate.
Θ(n log n) eventually grows more slowly than Θ(n²).
12. What does f(n) = O(g(n)) state about the growth of f(n)?
After some input size, f(n) stays at or above a positive constant multiple of g(n).
After some input size, f(n) stays at or below a positive constant multiple of g(n).
For every input size, f(n) and g(n) must have exactly equal values.
As the input grows, the ratio of f(n) to g(n) must approach zero.
13. An algorithm makes one pass through an array, performs constant work on each element, and must inspect every element. What is its tight running time?
Constant time, because the operation performed on each element is constant.
Linear time, because the amount of work grows in direct proportion to the array length.
Logarithmic time, because array elements can be accessed by index.
Quadratic time, because inspection and processing are two separate actions.
14. One loop processes all n items, and after it finishes, a second loop independently processes all n items. Both do constant work per item. What is the combined complexity?
O(n²), because there are two loops.
O(log n), because the work is split between loops.
O(n), because the two linear loop costs are added.
O(1), because each iteration performs constant work.
15. A binary search repeatedly discards half of a sorted array. What is its worst-case time complexity?
Linearithmic time, because each comparison is combined with a full pass.
Linear time, because every array element may need to be checked.
Logarithmic time, because the remaining search interval is halved each step.
Quadratic time, because two array boundaries are tracked.
16. A program has an outer loop that runs n times. On every outer iteration, an inner loop also runs n times and performs constant work. What is the total time complexity?
Constant time, because the work inside the inner loop is constant.
Quadratic time, because n inner iterations occur on each of n outer iterations.
Linear time, because both loops use the same input size.
Logarithmic time, because nested loops reduce the remaining input.