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

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

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

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

  1. AO(log n)
  2. BO(n)
  3. CO(1)
  4. DO(n²)
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 time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V³ × E)
6.Medium

What is the worst-case time complexity of quicksort?

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

  1. AIt can be solved by Dijkstra's algorithm with negated weights
  2. BIt is NP-hard
  3. CIt is always solvable in O(V + E)
  4. DIt is undecidable
8.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. CReaching the middle element takes O(n) steps, since there is no direct index access
  4. DBinary search needs at least twice the memory

Answer key

  1. 1. D · O(log n)
  2. 2. A · O(n + k)
  3. 3. B · O(n)
  4. 4. C · O(n log n)
  5. 5. A · O(V × E)
  6. 6. B · O(n²)
  7. 7. B · It is NP-hard
  8. 8. C · 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.