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 O(n²) algorithm takes 1 second for n = 1000. About how long does it take for n = 2000?

  1. A8 seconds
  2. B2 seconds
  3. C1 second
  4. D4 seconds
2.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²)
3.Easy

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

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

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

  1. AO(n log n)
  2. BO(n)
  3. CO(log n)
  4. DO(n²)
5.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)
6.Medium

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

  1. AO(mn)
  2. BO(2m+n)
  3. CO(mn log n)
  4. DO(m + n)
7.Hard

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

  1. ABecause the algorithm is randomised and its running time varies with each input
  2. BBecause it only works for W = 0
  3. CW is a number, so the time is exponential in the number of bits used to write W
  4. DBecause n is always small
8.Hard

A problem is NP-complete if it is:

  1. AImpossible to solve
  2. BIn NP and every NP problem reduces to it in polynomial time
  3. COutside NP but harder than all NP problems, such as the halting problem
  4. DSolvable in polynomial time

Answer key

  1. 1. D · 4 seconds
  2. 2. B · O(n log n)
  3. 3. A · O(n²)
  4. 4. A · O(n log n)
  5. 5. A · O(n²)
  6. 6. A · O(mn)
  7. 7. C · W is a number, so the time is exponential in the number of bits used to write W
  8. 8. B · In NP and every NP problem reduces to it in polynomial time

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