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

What is O(2ⁿ) growth called?

  1. ALinear
  2. BPolynomial
  3. CExponential
  4. DLogarithmic
3.Easy

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

  1. AInsertion sort
  2. BBubble sort
  3. CQuicksort
  4. DMerge sort
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(V³ × E)
  3. CO(E log V)
  4. DO(V × E)
5.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²)
  4. DO(n log n)
6.Medium

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

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

What did the Cook–Levin theorem establish?

  1. AThe Boolean satisfiability problem (SAT) is NP-complete
  2. BThe halting problem is undecidable
  3. CP is not equal to NP
  4. DEvery NP problem can be solved in exponential time
8.Hard

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

  1. ABecause the algorithm is randomised and its running time varies with each input
  2. BW is a number, so the time is exponential in the number of bits used to write W
  3. CBecause n is always small
  4. DBecause it only works for W = 0

Answer key

  1. 1. B · O(n)
  2. 2. C · Exponential
  3. 3. C · Quicksort
  4. 4. D · O(V × E)
  5. 5. C · O(n²)
  6. 6. A · O(n)
  7. 7. A · The Boolean satisfiability problem (SAT) is NP-complete
  8. 8. B · W is a number, so the time is exponential in the number of bits used to write W

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