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

What are the three steps of a divide-and-conquer algorithm?

  1. ADivide, conquer, combine
  2. BSort, search, return
  3. CRead, compute, write
  4. DGuess, check, repeat
3.Easy

What is O(2ⁿ) growth called?

  1. AExponential
  2. BPolynomial
  3. CLogarithmic
  4. DLinear
4.Medium

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

The lower bound for comparison-based sorting in the worst case is:

  1. AΩ(n)
  2. BΩ(n²)
  3. CΩ(n log n)
  4. DΩ(log n)
6.Medium

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

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

Which technique gives an expected O(n log n) running time for quicksort on any input?

  1. AAlways choosing the first element
  2. BChoosing the pivot uniformly at random
  3. CSorting the input before running quicksort
  4. DUsing recursion only on the left side
8.Hard

Why can Dijkstra's algorithm give wrong results when some edge weights are negative?

  1. AA vertex is finalised when extracted, but a later negative edge could still give it a shorter path
  2. BIt only works on undirected graphs
  3. CNegative numbers cannot be stored in a priority queue
  4. DIt goes into an infinite loop on every negative edge

Answer key

  1. 1. A · O(n + k)
  2. 2. A · Divide, conquer, combine
  3. 3. A · Exponential
  4. 4. D · O(1)
  5. 5. C · Ω(n log n)
  6. 6. D · O(log n)
  7. 7. B · Choosing the pivot uniformly at random
  8. 8. A · A vertex is finalised when extracted, but a later negative edge could still give it a shorter path

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