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 best-case time complexity of insertion sort, on an already sorted array?

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

What does it mean if an operation runs in O(1) time?

  1. AIt can only be run once
  2. BIt processes exactly one element per second of running time
  3. CIts running time does not grow with the input size
  4. DIt always takes exactly one second
3.Easy

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

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

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

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

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

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

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

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

Topological sorting is possible only for:

  1. AUndirected graphs
  2. BGraphs with negative weights
  3. CComplete graphs
  4. DDirected acyclic graphs
8.Hard

Why does binary search not give O(log n) time on a singly linked list?

  1. ABinary search needs at least twice the memory
  2. BReaching the middle element takes O(n) steps, since there is no direct index access
  3. CLinked lists cannot be sorted
  4. DComparisons on linked list nodes are slower

Answer key

  1. 1. B · O(n)
  2. 2. C · Its running time does not grow with the input size
  3. 3. D · O(log n)
  4. 4. B · O(log n)
  5. 5. B · O(n)
  6. 6. B · O(n log n)
  7. 7. D · Directed acyclic graphs
  8. 8. B · Reaching the middle element takes O(n) steps, since there is no direct index access

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