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 running time of counting sort for n integers in the range 0 to k?

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

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

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

What is the Big O of 3n² + 5n + 2?

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

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

What does the Floyd–Warshall algorithm compute, and how fast?

  1. AShortest paths between all pairs of vertices in O(V³)
  2. BA topological order in O(V²)
  3. CShortest paths from one source vertex to all others in O(V + E)
  4. DA minimum spanning tree in O(E log V)
6.Medium

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

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

How do n! and 2ⁿ compare for large n?

  1. An! grows faster than 2ⁿ
  2. BThey grow at the same rate
  3. Cn! is O(n²)
  4. D2ⁿ grows faster than n!
8.Hard

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

  1. AΘ(nlog₂ 7), about n2.81
  2. BΘ(n³)
  3. CΘ(n2)
  4. DΘ(n² log n)

Answer key

  1. 1. C · O(n + k)
  2. 2. A · O(n)
  3. 3. B · O(n²)
  4. 4. A · O(n)
  5. 5. A · Shortest paths between all pairs of vertices in O(V³)
  6. 6. A · O(n log n)
  7. 7. A · n! grows faster than 2ⁿ
  8. 8. A · Θ(nlog₂ 7), about n2.81

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