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 are the three steps of a divide-and-conquer algorithm?

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

Which notation describes an upper bound on growth?

  1. ABig O
  2. BBig Theta
  3. CLittle omega
  4. DBig Omega
3.Easy

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

  1. ABubble sort
  2. BHeap sort
  3. CMerge sort
  4. DQuicksort
4.Medium

What is the worst-case time complexity of quicksort?

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

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

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

Why do many library sorting routines switch to insertion sort for very small subarrays?

  1. AInsertion sort is O(n log n) in the worst case
  2. BInsertion sort has little overhead and is fast on small or nearly sorted inputs
  3. CInsertion sort uses less memory than any other sorting algorithm on large inputs
  4. DRecursive algorithms cannot handle arrays below 10 elements
7.Hard

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

  1. AW is a number, so the time is exponential in the number of bits used to write W
  2. BBecause n is always small
  3. CBecause the algorithm is randomised and its running time varies with each input
  4. DBecause it only works for W = 0
8.Hard

Using the master theorem, T(n) = 8T(n/2) + O(n²) solves to:

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

Answer key

  1. 1. B · Divide, conquer, combine
  2. 2. A · Big O
  3. 3. A · Bubble sort
  4. 4. C · O(n²)
  5. 5. B · O(log n)
  6. 6. B · Insertion sort has little overhead and is fast on small or nearly sorted inputs
  7. 7. A · W is a number, so the time is exponential in the number of bits used to write W
  8. 8. C · Θ(n³)

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