Algorithms & complexity worksheet with answers

Free printable Algorithms & complexity worksheet: 8 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy

What is the worst-case time complexity of merge sort?

  1. AO(log n)
  2. BO(n log n)
  3. CO(n)
  4. DO(n²)
2.Easy

What is memoisation?

  1. AWriting comments next to each line of code
  2. BConverting recursion into an equivalent loop automatically so no call stack is needed
  3. CFreeing memory after a function returns
  4. DStoring the results of function calls so repeated calls are answered from memory
3.Easy

How much extra memory does a standard array-based merge sort use?

  1. AO(n²)
  2. BO(1)
  3. CO(log n)
  4. DO(n)
4.Medium

Which sorting algorithm is stable?

  1. AMerge sort
  2. BQuicksort (typical in-place version)
  3. CHeap sort
  4. DSelection sort (typical version)
5.Medium

The lower bound for comparison-based sorting in the worst case is:

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n²)
6.Medium

What does the recurrence T(n) = 2T(n/2) + O(1) solve to?

  1. AO(n²)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
7.Hard

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

  1. AΘ(n³)
  2. BΘ(n2)
  3. CΘ(nlog₂ 7), about n2.81
  4. DΘ(n² log n)
8.Hard

Which bound is correct for log(n!)?

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(n)
  4. DΘ(log n)

Answer key

  1. 1. B · O(n log n)
  2. 2. D · Storing the results of function calls so repeated calls are answered from memory
  3. 3. D · O(n)
  4. 4. A · Merge sort
  5. 5. A · Ω(n log n)
  6. 6. D · O(n)
  7. 7. C · Θ(nlog₂ 7), about n2.81
  8. 8. A · Θ(n log n)

Full step-by-step solutions: practise this topic on examproblems.com.