Suitability of Algorithms (OCR A-Level Computer Science): Revision Notes

Suitability of Algorithms

Overview

Different algorithms can solve the same problem, but they may vary significantly in their efficiency. Efficiency is typically measured in terms of execution time (speed) and space (memory usage). Choosing the most suitable algorithm for a task depends on the problem's requirements, such as handling large data sets quickly or minimising memory usage.

Algorithm Efficiency

Time Complexity:

Measures the time an algorithm takes to run as a function of the input size.

• Common time complexities:
  • O(1): Constant time
  • O(log n): Logarithmic time
  • O(n): Linear time
  • O(n²): Quadratic time
  • O(2ⁿ): Exponential time

Space Complexity:

Measures the amount of memory an algorithm uses during execution.

• Includes memory for input data, temporary variables, and call stack (for recursion).

Factors Influencing Suitability

• Input Size: Large inputs may require algorithms with lower time complexity to ensure acceptable performance.
• Available Memory: Algorithms with high space complexity might not be suitable for memory-constrained systems.
• Task Requirements: Some tasks prioritise speed, while others prioritise minimising memory usage or balancing both.

Comparing Algorithms

When comparing algorithms, consider how they behave under different conditions, such as:

• Small vs. large data sets.
• Best-case, average-case, and worst-case scenarios.

Examples of Algorithm Comparisons

Example 1: Sorting Algorithms

Algorithm	Time Complexity	Space Complexity	Suitability
Bubble Sort	O(n²)	O(1)	Suitable for small data sets, low memory.
Merge Sort	O(n log n)	O(n)	Efficient for large data sets but uses more memory.
Quick Sort	O(n log n) avg, O(n²) worst	O(log n)	Fast for most cases, but risky for poorly ordered data.

Scenario:

For a small data set with limited memory, Bubble Sort may be suitable. For a large data set, Merge Sort would typically perform better due to its faster time complexity.

Example 2: Searching Algorithms

Algorithm	Time Complexity	Space Complexity	Suitability
Linear Search	O(n)	O(1)	Simple, works on unsorted data. Suitable for small data sets.
Binary Search	O(log n)	O(1)	Requires sorted data but very efficient for large data sets.

Scenario:

For unsorted data, Linear Search is the only option unless you first sort the data (which adds time). For sorted data, Binary Search is significantly faster for large data sets.

Example 3: Recursive vs Iterative Algorithms

Task	Recursive Approach	Iterative Approach	Suitability
Calculating Factorials	O(n) time, O(n) space	O(n) time, O(1) space	Iterative is more memory-efficient.
Fibonacci Sequence	O(2ⁿ) time, O(n) space	O(n) time, O(1) space (DP)	Iterative with dynamic programming is faster and uses less memory.

Analysing Algorithms on Different Data Sets

Consider how an algorithm performs across various data sizes:

• Small Data Sets: Simpler algorithms with higher time complexity (e.g., Bubble Sort) may suffice.
• Large Data Sets: More efficient algorithms with better time complexity (e.g., Merge Sort) are essential to maintain reasonable execution times.
• Memory Constraints: If memory is limited, prefer algorithms with lower space complexity.

Note Summary