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 time complexity of binary search on a sorted array?

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

What does the worst-case running time of an algorithm describe?

  1. AThe maximum time it takes over all inputs of size n
  2. BThe time it takes on the smallest input
  3. CThe expected time it takes on a random input of size n
  4. DThe time it takes on a slow computer
3.Easy

What does binary search require of its input?

  1. AThe array must be sorted
  2. BThe array must have no more than 1000 elements
  3. CThe array length must be a power of two
  4. DThe array must contain only positive numbers
4.Medium

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

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

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(2ⁿ)
  4. DO(log n)
7.Hard

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

  1. ALinked lists cannot be sorted
  2. BBinary search needs at least twice the memory
  3. CComparisons on linked list nodes are slower
  4. DReaching the middle element takes O(n) steps, since there is no direct index access
8.Hard

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

  1. AO(n) time and O(n) space
  2. BO(log n) time and O(n) space
  3. CO(n) time and O(1) space
  4. DO(2ⁿ) time and O(1) space

Answer key

  1. 1. D · O(log n)
  2. 2. A · The maximum time it takes over all inputs of size n
  3. 3. A · The array must be sorted
  4. 4. C · O(n²)
  5. 5. C · O(n)
  6. 6. B · O(n)
  7. 7. D · Reaching the middle element takes O(n) steps, since there is no direct index access
  8. 8. C · O(n) time and O(1) space

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