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 does it mean if an operation runs in O(1) time?

  1. AIt can only be run once
  2. BIts running time does not grow with the input size
  3. CIt always takes exactly one second
  4. DIt processes exactly one element per second of running time
2.Easy

What is the worst-case time complexity of insertion sort?

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

What is log₂ 1024?

  1. A12
  2. B32
  3. C512
  4. D10
4.Medium

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

  1. AO(k n log n)
  2. BO(nk)
  3. CO(n log n + k log n)
  4. DO(n + k)
5.Medium

Dynamic programming is useful when a problem has:

  1. AOverlapping subproblems and optimal substructure
  2. BNo subproblems at all, so it can be solved in one step
  3. COnly random inputs
  4. DA single loop
6.Medium

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

  1. AO(n log n)
  2. BO(n)
  3. CO(n²)
  4. DO(2ⁿ)
7.Hard

Topological sorting is possible only for:

  1. AUndirected graphs
  2. BDirected acyclic graphs
  3. CGraphs with negative weights
  4. DComplete graphs
8.Hard

Which statement about P and NP is correct?

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

Answer key

  1. 1. B · Its running time does not grow with the input size
  2. 2. D · O(n²)
  3. 3. D · 10
  4. 4. C · O(n log n + k log n)
  5. 5. A · Overlapping subproblems and optimal substructure
  6. 6. C · O(n²)
  7. 7. B · Directed acyclic graphs
  8. 8. B · Every problem in P is also in NP

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