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

A problem is usually called tractable if:

  1. AIt can only be solved by trying every possibility
  2. BIt can be solved in polynomial time
  3. CIt has no solution
  4. DIt can be solved in constant time
2.Easy

What is the running time of counting sort for n integers in the range 0 to k?

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

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

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

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

  1. ADijkstra's algorithm
  2. BDepth-first search
  3. CBellman–Ford is required in all cases
  4. DKruskal's algorithm
7.Hard

Which statement about little-o notation is correct?

  1. An² = o(n)
  2. B2n = o(n), because 2n grows slowly
  3. Cn = o(n), since every function is little-o of itself
  4. Dn = o(n²), but n is not o(n)
8.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²)
  4. DΘ(n log² n)

Answer key

  1. 1. B · It can be solved in polynomial time
  2. 2. D · O(n + k)
  3. 3. D · O(n²)
  4. 4. A · O(V × E)
  5. 5. B · O(n log n)
  6. 6. A · Dijkstra's algorithm
  7. 7. D · n = o(n²), but n is not o(n)
  8. 8. D · Θ(n log² n)

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