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 the worst-case time complexity of merge sort?

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

What is the time complexity of depth-first search on a graph stored as adjacency lists?

  1. AO(V + E)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V²)
3.Easy

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

  1. AAbout n²
  2. BAbout log₂ n
  3. CAbout n
  4. DAbout n / 2
4.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 log n)
  3. CO(d(n + k))
  4. DO(n²)
5.Medium

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

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

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

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

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

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

Which bound is correct for log(n!)?

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

Answer key

  1. 1. B · O(n log n)
  2. 2. A · O(V + E)
  3. 3. B · About log₂ n
  4. 4. C · O(d(n + k))
  5. 5. D · O(n)
  6. 6. D · O(n log n)
  7. 7. C · Θ(n log² n)
  8. 8. A · Θ(n log n)

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