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

How much extra memory does a standard array-based merge sort use?

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

Which design strategy does merge sort use?

  1. ADynamic programming
  2. BBrute force
  3. CDivide and conquer
  4. DGreedy choice
3.Easy

What is O(2ⁿ) growth called?

  1. ALogarithmic
  2. BExponential
  3. CPolynomial
  4. DLinear
4.Medium

How many levels does the recursion of merge sort have for an array of n elements?

  1. AAbout n
  2. BAbout √n
  3. CAbout n / 2
  4. DAbout log₂ n
5.Medium

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

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

  1. AO(n² 2ⁿ)
  2. BO(n³)
  3. CO(2n²)
  4. DO(n!)
8.Hard

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

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

Answer key

  1. 1. C · O(n)
  2. 2. C · Divide and conquer
  3. 3. B · Exponential
  4. 4. D · About log₂ n
  5. 5. D · O(log n)
  6. 6. D · O(V × E)
  7. 7. A · O(n² 2ⁿ)
  8. 8. D · W is a number, so the time is exponential in the number of bits used to write W

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