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 sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

  1. AMerge sort
  2. BBubble sort
  3. CHeap sort
  4. DQuicksort
2.Easy

What does binary search require of its input?

  1. AThe array must have no more than 1000 elements
  2. BThe array must be sorted
  3. CThe array must contain only positive numbers
  4. DThe array length must be a power of two
3.Easy

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

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

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

  1. ADepth-first search
  2. BKruskal's algorithm
  3. CBellman–Ford is required in all cases
  4. DDijkstra's algorithm
6.Medium

Dynamic programming is useful when a problem has:

  1. AA single loop
  2. BOnly random inputs
  3. COverlapping subproblems and optimal substructure
  4. DNo subproblems at all, so it can be solved in one step
7.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
8.Hard

What is the amortised cost of incrementing a binary counter, given that one increment may flip many bits?

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

Answer key

  1. 1. B · Bubble sort
  2. 2. B · The array must be sorted
  3. 3. B · O(n²)
  4. 4. A · O(n)
  5. 5. D · Dijkstra's algorithm
  6. 6. C · Overlapping subproblems and optimal substructure
  7. 7. B · Every problem in P is also in NP
  8. 8. D · O(1) per increment

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