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 loop that never ends
  3. CA type of data structure
  4. DA function that calls itself on smaller inputs
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²)
  4. DO(V × E)
3.Easy

Which design strategy does merge sort use?

  1. ABrute force
  2. BDivide and conquer
  3. CDynamic programming
  4. DGreedy choice
4.Medium

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

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

How many levels does the recursion of merge sort have for an array of n elements?

  1. AAbout √n
  2. BAbout n / 2
  3. CAbout log₂ n
  4. DAbout n
6.Medium

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

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  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. BComparisons on linked list nodes are slower
  3. CBinary search needs at least twice the memory
  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(log n) time and O(n) space
  2. BO(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 · A function that calls itself on smaller inputs
  2. 2. A · O(V + E)
  3. 3. B · Divide and conquer
  4. 4. D · O(n)
  5. 5. C · About log₂ n
  6. 6. A · 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.