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 time complexity of finding the largest value in an unsorted array of n numbers?

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

Which of these running times is polynomial?

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

Which notation describes a lower bound on growth?

  1. AΘ (Big Theta)
  2. Bo (little o)
  3. CΩ (Big Omega)
  4. DO (Big O)
4.Medium

The lower bound for comparison-based sorting in the worst case is:

  1. AΩ(log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(n log n)
5.Medium

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

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

How does the Bellman–Ford algorithm detect a negative-weight cycle reachable from the source?

  1. AAfter V − 1 rounds, it checks whether any edge can still be relaxed
  2. BIt counts the cycles with depth-first search
  3. CIt runs Dijkstra's algorithm twice and compares the two distance results
  4. DIt checks whether any edge has a negative weight
8.Hard

Which definition of the class P is correct?

  1. AProblems whose solutions can be checked but never found in polynomial time
  2. BDecision problems solvable by a deterministic algorithm in polynomial time
  3. CProblems that can be solved in parallel
  4. DProblems that need exponential time on every computer

Answer key

  1. 1. A · O(n)
  2. 2. D · O(n³)
  3. 3. C · Ω (Big Omega)
  4. 4. D · Ω(n log n)
  5. 5. A · O(n²)
  6. 6. D · O(V × E)
  7. 7. A · After V − 1 rounds, it checks whether any edge can still be relaxed
  8. 8. B · Decision problems solvable by a deterministic algorithm in polynomial time

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