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(n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n log n)
2.Easy

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

What is log₂ 1024?

  1. A12
  2. B512
  3. C10
  4. D32
4.Medium

Dynamic programming is useful when a problem has:

  1. ANo subproblems at all, so it can be solved in one step
  2. BOnly random inputs
  3. COverlapping subproblems and optimal substructure
  4. DA single loop
5.Medium

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

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

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

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

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

  1. AAt most twice the size of a minimum vertex cover
  2. BAlways a minimum vertex cover
  3. CAt most log n times the minimum
  4. DOf unknown quality compared to the optimum
8.Hard

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

  1. AIt counts the cycles with depth-first search
  2. BAfter V − 1 rounds, it checks whether any edge can still be relaxed
  3. CIt checks whether any edge has a negative weight
  4. DIt runs Dijkstra's algorithm twice and compares the two distance results

Answer key

  1. 1. D · O(n log n)
  2. 2. B · O(n)
  3. 3. C · 10
  4. 4. C · Overlapping subproblems and optimal substructure
  5. 5. B · O(2ⁿ)
  6. 6. B · O(n²)
  7. 7. A · At most twice the size of a minimum vertex cover
  8. 8. B · After V − 1 rounds, it checks whether any edge can still be relaxed

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