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 binary search on a sorted array?

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

What does the average-case running time describe?

  1. AThe time for an input of average length
  2. BThe time on the most common computer
  3. CThe middle value between the best-case and worst-case running times
  4. DThe expected time over a given distribution of inputs of size n
3.Easy

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

  1. A6 seconds
  2. B12 seconds
  3. C3 seconds
  4. D9 seconds
4.Medium

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

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

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

  1. AGreedy uses 4 coins; the optimum is 3
  2. BGreedy uses 3 coins; the optimum is 3
  3. CGreedy uses 3 coins; the optimum is 2
  4. DGreedy uses 2 coins; the optimum is 2
6.Medium

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

Which two things must be shown to prove that a decision problem X is NP-complete?

  1. AX has no polynomial algorithm, and X is decidable
  2. BX is in P, and X reduces to SAT
  3. CX reduces to a problem in P, and X is in NP
  4. DX is in NP, and a known NP-complete problem reduces to X in polynomial time
8.Hard

What is the time complexity of building a binary heap from n unsorted elements with the bottom-up method?

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

Answer key

  1. 1. A · O(log n)
  2. 2. D · The expected time over a given distribution of inputs of size n
  3. 3. A · 6 seconds
  4. 4. D · O(2ⁿ)
  5. 5. C · Greedy uses 3 coins; the optimum is 2
  6. 6. A · O(n)
  7. 7. D · X is in NP, and a known NP-complete problem reduces to X in polynomial time
  8. 8. A · O(n)

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