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

An algorithm with two nested loops, each running n times, typically has which complexity?

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

Which of these running times is polynomial?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
3.Easy

What is an algorithm?

  1. AA finite sequence of well-defined steps that solves a problem
  2. BAny computer program that has a graphical interface
  3. CA programming language designed for writing mathematical formulas
  4. DA data structure that stores numbers
4.Medium

Breadth-first search on an unweighted graph finds:

  1. AThe minimum spanning tree
  2. BShortest paths in graphs that contain negative edge weights
  3. CA topological order in all graphs
  4. DShortest paths in number of edges from the start node
5.Medium

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

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

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

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

Insertion sort runs in O(n) on sorted input. Does this contradict the Ω(n log n) lower bound for comparison sorting?

  1. ANo, the lower bound applies to the worst case over all inputs, not to every input
  2. BNo, because insertion sort is not a comparison sort
  3. CYes, the lower bound is therefore wrong
  4. DYes, but only for arrays shorter than 100
8.Hard

Which statement about little-o notation is correct?

  1. An = o(n²), but n is not o(n)
  2. Bn² = o(n)
  3. C2n = o(n), because 2n grows slowly
  4. Dn = o(n), since every function is little-o of itself

Answer key

  1. 1. B · O(n²)
  2. 2. C · O(n³)
  3. 3. A · A finite sequence of well-defined steps that solves a problem
  4. 4. D · Shortest paths in number of edges from the start node
  5. 5. D · O(n²)
  6. 6. A · O(n)
  7. 7. A · No, the lower bound applies to the worst case over all inputs, not to every input
  8. 8. A · n = o(n²), but n is not o(n)

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