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

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

  1. ABubble sort
  2. BQuicksort
  3. CInsertion sort
  4. DMerge sort
3.Easy

What is the base case of a recursive function?

  1. AThe first line of the function
  2. BThe call that uses the most memory
  3. CThe case with the largest input, which is handled before any recursive calls
  4. DA case that is answered directly without making another recursive call
4.Medium

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

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

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

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

Which definition of the class NP is correct?

  1. AProblems that cannot be solved in polynomial time
  2. BDecision problems whose yes-answers can be verified in polynomial time given a certificate
  3. CProblems that no algorithm can solve
  4. DProblems that are not polynomial
8.Hard

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

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

Answer key

  1. 1. B · O(n²)
  2. 2. B · Quicksort
  3. 3. D · A case that is answered directly without making another recursive call
  4. 4. C · O(log n)
  5. 5. C · Ω(n log n)
  6. 6. C · O(n log n)
  7. 7. B · Decision problems whose yes-answers can be verified in polynomial time given a certificate
  8. 8. D · Θ(n³)

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