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 notation describes an upper bound on growth?

  1. ABig Theta
  2. BBig Omega
  3. CLittle omega
  4. DBig O
2.Easy

Which complexity class grows fastest for large n?

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

Which of these grows slowest as n becomes large?

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

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

What is the running time of LSD radix sort on n integers with d digits in base k?

  1. AO(dn log k)
  2. BO(n²)
  3. CO(d(n + k))
  4. DO(n log n)
6.Medium

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

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

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

  1. ANeither variant
  2. BBoth variants
  3. CThe 0/1 knapsack, where items must always be taken whole
  4. DThe fractional knapsack, where items may be split
8.Hard

Which definition of the class NP is correct?

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

Answer key

  1. 1. D · Big O
  2. 2. D · O(2ⁿ)
  3. 3. C · O(log n)
  4. 4. D · O(n)
  5. 5. C · O(d(n + k))
  6. 6. D · O(n)
  7. 7. D · The fractional knapsack, where items may be split
  8. 8. A · Decision problems whose yes-answers can be verified in polynomial time given a certificate

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