Algorithms & Complexity Quiz

Grade 12 · Technology · Quiz

Challenge your understanding of Big O analysis, algorithm design paradigms, and computational complexity theory.

Questions

1. Binary search on a sorted array of 1,024 elements requires at most how many comparisons?

   1. 10
   2. 32
   3. 512
   4. 1024
   Show answer

   Answer: 10

   Binary search halves the search space each step; log₂(1024) = 10, so at most 10 comparisons are needed.

2. Which of the following algorithms is NOT an example of the dynamic programming paradigm?

   1. Longest Common Subsequence
   2. 0/1 Knapsack
   3. Dijkstra's Shortest Path
   4. Floyd-Warshall All-Pairs Shortest Path
   Show answer

   Answer: Dijkstra's Shortest Path

   Dijkstra's is a greedy algorithm, not DP. LCS, 0/1 Knapsack, and Floyd-Warshall all use DP tables to store subproblem results.

3. Every NP-complete problem can currently be solved in polynomial time.

   Show answer

   Answer: False

   No polynomial-time algorithm is known for any NP-complete problem. Whether one exists is the unsolved P vs NP question.

4. What does it mean for an algorithm to have O(1) space complexity?

   1. It uses no memory at all
   2. Its memory usage is constant regardless of input size
   3. It runs in constant time
   4. It uses memory proportional to the square of the input
   Show answer

   Answer: Its memory usage is constant regardless of input size

   O(1) space means the algorithm uses a fixed amount of extra memory regardless of input size — for example, an in-place swap.

5. An algorithm that solves a problem by making the locally optimal choice at each step, without reconsidering past choices, is called a ______ algorithm.

   Show answer

   Answer: greedy

   Greedy algorithms commit to a local optimum at each step without backtracking; they work when the problem has the greedy-choice property.

6. Which recurrence relation correctly describes the time complexity of merge sort?

   1. T(n) = T(n-1) + O(1)
   2. T(n) = 2T(n/2) + O(n)
   3. T(n) = T(n/2) + O(1)
   4. T(n) = 2T(n-1) + O(n)
   Show answer

   Answer: T(n) = 2T(n/2) + O(n)

   Merge sort divides into 2 halves (2T(n/2)) and merges in linear time (O(n)), giving T(n) = 2T(n/2) + O(n), which resolves to O(n log n).

7. Backtracking algorithms always explore every possible candidate solution before returning an answer.

   Show answer

   Answer: False

   Backtracking prunes branches early when a constraint is violated, avoiding exploration of invalid candidates — this is what makes it more efficient than brute force.

8. Which statement about NP-hard problems is correct?

   1. All NP-hard problems are in NP
   2. NP-hard problems cannot be approximated
   3. Solving one NP-hard problem in polynomial time would imply P = NP
   4. NP-hard problems have no known algorithms
   Show answer

   Answer: Solving one NP-hard problem in polynomial time would imply P = NP

   NP-hard problems are at least as hard as any NP problem; solving one in polynomial time would prove P = NP. Not all NP-hard problems are in NP (some are undecidable).

Get a personalized course on Algorithms & Complexity built around your child.