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 O
  3. CLittle omega
  4. DBig Omega
2.Easy

What is the time complexity of binary search on a sorted array?

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

Which notation describes a lower bound on growth?

  1. AO (Big O)
  2. BΩ (Big Omega)
  3. Co (little o)
  4. DΘ (Big Theta)
4.Medium

A greedy algorithm:

  1. ATries every possible solution
  2. BMakes the locally best choice at each step
  3. CAlways gives the optimal solution
  4. DUses only recursion
5.Medium

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

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

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

  1. AO(n!)
  2. BO(2n²)
  3. CO(n² 2ⁿ)
  4. DO(n³)
8.Hard

A problem is NP-complete if it is:

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

Answer key

  1. 1. B · Big O
  2. 2. A · O(log n)
  3. 3. B · Ω (Big Omega)
  4. 4. B · Makes the locally best choice at each step
  5. 5. B · O(n)
  6. 6. C · O(n)
  7. 7. C · O(n² 2ⁿ)
  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.