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

Which of these running times is polynomial?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
2.Easy

An algorithm with two nested loops, each running n times, typically has which complexity?

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

  1. ABubble sort
  2. BMerge sort
  3. CHeap sort
  4. DQuicksort
4.Medium

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

  1. AO(nk)
  2. BO(n + k)
  3. CO(n log n + k log n)
  4. DO(k n log 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(E log V)
  3. CO(V + E)
  4. DO(V × E)
6.Medium

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

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

  1. AΘ(n²)
  2. BΘ(n log² n)
  3. CΘ(n log n)
  4. DΘ(n)
8.Hard

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

  1. AThe fractional knapsack, where items may be split
  2. BBoth variants
  3. CNeither variant
  4. DThe 0/1 knapsack, where items must always be taken whole

Answer key

  1. 1. C · O(n³)
  2. 2. D · O(n²)
  3. 3. A · Bubble sort
  4. 4. C · O(n log n + k log n)
  5. 5. D · O(V × E)
  6. 6. A · O(n)
  7. 7. B · Θ(n log² n)
  8. 8. A · The fractional knapsack, where items may be split

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