Revise Computingrevisecomputing.co.uk
Free student revisionSee questionsFor schoolsSchool enquiry
Free revisionSee questionsFor schoolsSchool enquiry
Knowledge/A Level/H446/02 Algorithms and programming/Computational Methods/Use of divide and conquer

Use of divide and conquer

Use of divide and conquer.

2.2.2 Computational Methods

Computational Methods — Note 4 of 6

Candidates need to understand how divide and conquer splits a task into smaller tasks that are then tackled. Candidates also need to identify how tasks can be carried out simultaneously to produce a solution.

What you need to know

Divide and conquer repeatedly splits a problem into smaller instances of the same problem, solves them and combines the results. It is the basis of several efficient algorithms, such as binary search, merge sort and quick sort.

What to know

  • Binary search halves the data with each comparison, so it is very efficient: O(log n).
  • Merge sort splits a list into halves until each part has one item, then merges them back in order.
  • Quick sort partitions the list around a pivot and sorts each part.
  • Because the sub-problems are of the same type, divide and conquer is often implemented recursively.
  • Independent sub-problems can be solved at the same time on different processors.

Key terms

Divide and conquer

A technique that repeatedly divides a problem into smaller sub-problems of the same type, solves (conquers) each, and combines the solutions.

Exam technique

  • Tip:Explain how halving the problem each time reduces the number of steps needed, compared with dealing with every item in turn.
← Previous noteProblem decomposition2.2.2 Computational MethodsNext note →Use of abstraction2.2.2 Computational Methods

Back to Computational Methods

Computational Methods

Note 4 of 6

  1. 1Features that make a problem solvable by computational methods
  2. 2Problem recognition
  3. 3Problem decomposition
  4. 4Use of divide and conquer
  5. 5Use of abstraction
  6. 6Backtracking, data mining, heuristics, performance modelling, pipelining and visualisation
Topic overview