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

What is recursion?

  1. AA sorting method
  2. BA type of data structure
  3. CA function that calls itself on smaller inputs
  4. DA loop that never ends
2.Easy

A problem is usually called tractable if:

  1. AIt can be solved in constant time
  2. BIt can be solved in polynomial time
  3. CIt can only be solved by trying every possibility
  4. DIt has no solution
3.Easy

What is the running time of counting sort for n integers in the range 0 to k?

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

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

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

What is the worst-case time complexity of quicksort?

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

Why is the average lookup in a hash table O(1) but the worst case O(n)?

  1. AKeys must be sorted first
  2. BArrays have O(n) access
  3. CHash functions are slow
  4. DMany keys may collide into the same bucket
8.Hard

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

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

Answer key

  1. 1. C · A function that calls itself on smaller inputs
  2. 2. B · It can be solved in polynomial time
  3. 3. D · O(n + k)
  4. 4. C · O(n log n)
  5. 5. D · O(n²)
  6. 6. C · O(n)
  7. 7. D · Many keys may collide into the same bucket
  8. 8. B · Θ(n log² n)

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