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

Which complexity class grows fastest for large n?

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

  1. AMerge sort
  2. BHeap sort
  3. CBubble sort
  4. DQuicksort
3.Easy

Which design strategy does merge sort use?

  1. ADivide and conquer
  2. BBrute force
  3. CDynamic programming
  4. DGreedy choice
4.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)
5.Medium

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

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

A greedy algorithm:

  1. AUses only recursion
  2. BTries every possible solution
  3. CAlways gives the optimal solution
  4. DMakes the locally best choice at each step
7.Hard

For which knapsack variant does the greedy rule "take items in order of value per weight" always give an optimal answer?

  1. AThe fractional knapsack, where items may be split
  2. BBoth variants
  3. CThe 0/1 knapsack, where items must always be taken whole
  4. DNeither variant
8.Hard

Why does any comparison-based search in a sorted array need Ω(log n) comparisons in the worst case?

  1. AA decision tree with n possible outcomes must have depth at least log₂ n
  2. BEvery element must be compared at least once
  3. CBinary search is the only possible algorithm, and it needs log₂ n comparisons
  4. DComparisons take logarithmic time each

Answer key

  1. 1. C · O(2ⁿ)
  2. 2. C · Bubble sort
  3. 3. A · Divide and conquer
  4. 4. B · O(n²)
  5. 5. A · O(n)
  6. 6. D · Makes the locally best choice at each step
  7. 7. A · The fractional knapsack, where items may be split
  8. 8. A · A decision tree with n possible outcomes must have depth at least log₂ n

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