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 be solved in constant time
  2. BIt can be solved in polynomial time
  3. CIt has no solution
  4. DIt can only be solved by trying every possibility
2.Easy

Which of these grows slowest as n becomes large?

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

Which of these running times is polynomial?

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

What is the time complexity of: for i = 1 to n: for j = 1 to i: do O(1) work?

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

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

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

Breadth-first search on an unweighted graph finds:

  1. AThe minimum spanning tree
  2. BA topological order in all graphs
  3. CShortest paths in number of edges from the start node
  4. DShortest paths in graphs that contain negative edge weights
7.Hard

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

  1. AO(log n) time and O(n) space
  2. BO(n) time and O(1) space
  3. CO(2ⁿ) time and O(1) space
  4. DO(n) time and O(n) space
8.Hard

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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

Answer key

  1. 1. B · It can be solved in polynomial time
  2. 2. B · O(log n)
  3. 3. D · O(n³)
  4. 4. A · O(n²)
  5. 5. A · About log₂ n
  6. 6. C · Shortest paths in number of edges from the start node
  7. 7. B · O(n) time and O(1) space
  8. 8. D · O(n log n)

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