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 best-case time complexity of insertion sort, on an already sorted array?

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

A problem is usually called tractable if:

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

Which notation describes a lower bound on growth?

  1. Ao (little o)
  2. BΩ (Big Omega)
  3. CO (Big O)
  4. DΘ (Big Theta)
4.Medium

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

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

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

What is the worst-case time complexity of quicksort?

  1. AO(n log n)
  2. BO(n²)
  3. CO(n)
  4. DO(log n)
7.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. CIt goes into an infinite loop on every negative edge
  4. DNegative numbers cannot be stored in a priority queue
8.Hard

Which statement about P and NP is correct?

  1. ANP problems cannot be verified quickly
  2. BIt has been proven that P ≠ NP
  3. CNP means "not polynomial"
  4. DEvery problem in P is also in NP

Answer key

  1. 1. A · O(n)
  2. 2. D · It can be solved in polynomial time
  3. 3. B · Ω (Big Omega)
  4. 4. C · O(n)
  5. 5. B · O(n³)
  6. 6. B · O(n²)
  7. 7. A · A vertex is finalised when extracted, but a later negative edge could still give it a shorter path
  8. 8. D · Every problem in P is also in NP

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