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

Which complexity class grows fastest for large n?

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

Which notation describes a lower bound on growth?

  1. AO (Big O)
  2. Bo (little o)
  3. CΩ (Big Omega)
  4. DΘ (Big Theta)
3.Easy

What is an algorithm?

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

Which sorting algorithm is stable?

  1. AQuicksort (typical in-place version)
  2. BHeap sort
  3. CMerge sort
  4. DSelection sort (typical version)
5.Medium

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

  1. AAn array that is already sorted
  2. BAn array whose elements are all different
  3. CAn array in random order
  4. DAn array of length 2
6.Medium

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

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

How do n! and 2ⁿ compare for large n?

  1. AThey grow at the same rate
  2. Bn! grows faster than 2ⁿ
  3. C2ⁿ grows faster than n!
  4. Dn! is O(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. D · O(2ⁿ)
  2. 2. C · Ω (Big Omega)
  3. 3. A · A finite sequence of well-defined steps that solves a problem
  4. 4. C · Merge sort
  5. 5. A · An array that is already sorted
  6. 6. C · O(n)
  7. 7. B · n! grows faster than 2ⁿ
  8. 8. A · Θ(n log n)

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