2.3 Algorithms

All of 2.3 is in both AS and A Level, but A Level may go deeper into algorithm complexity (time/space complexity). At AS, you need to understand the basic principles and be able to apply them, but not necessarily with the same depth of mathematical formalism.

2.3.1 Analysis and design of algorithms

• Requirements analysis:

  • Determining what the algorithm must do (inputs, outputs, constraints).

• Design:

  • Outlining steps (pseudocode, flowcharts, structured English).

  • Identifying data structures required.

• Correctness:

  • Ensuring the algorithm meets all specified requirements (e.g., edge cases, invalid inputs).

2.3.2 Standard algorithms (searching and sorting)

• Searching:

  • Linear search: Step through each element until target is found or the list ends.

  • Binary search: Repeatedly divide a sorted list in half, discarding the half that cannot contain the item.

• Sorting:

  • Bubble sort: Repeatedly swap adjacent out-of-order elements.

  • Insertion sort: Build a sorted portion one element at a time, inserting new elements in the correct place.

  • Merge sort: Divide the list into halves, recursively sort, then merge sorted halves.

  • (A Level often includes additional detail on time complexity of these algorithms.)

2.3.3 Algorithm efficiency (time complexity, space complexity)

• Basic Big-O notation at AS Level (e.g., O(n), O(n log n), O(n²)):

  • Compare efficiency qualitatively (e.g., linear vs. quadratic).

• Time complexity: How the execution time grows with input size.

• Space complexity: How the memory usage grows with input size.

• Trade-offs: Some algorithms are faster but use more memory; others use less memory but may be slower.

2.3.4 Comparing and improving algorithms

• Comparisons: Evaluate algorithms based on:

  • Complexity (time/space).

  • Scalability, clarity, and ease of implementation.

• Improving:

  • Adjust data structures.

  • Optimize logic (reduce repeated computation).

  • Parallelize parts of the algorithm (where possible).