The Uses of Algorithms

This section provides A-Level Computer Science notes on the Uses of Algorithms.

Analysis and Design of Algorithms

What is an Algorithm?

An algorithm is a step-by-step set of instructions used to solve a problem or perform a task.

Designing an Algorithm

When designing an algorithm, you should:

• Identify inputs and outputs
• Break the problem into smaller steps (decomposition)
• Consider efficiency (time and space)
• Ensure the solution is logical, clear, and unambiguous 

Example

Searching for a number in a list:

• Input: list + target value
• Output: position or “not found”
• Steps: choose search method (e.g., linear or binary) 

Suitability of Algorithms

Key Factors

• Size of dataset (small vs large)
• Structure of data (sorted vs unsorted)
• Time efficiency (speed)
• Space efficiency (memory usage) 

Examples

• Binary search → efficient but requires sorted data
• Linear search → works on any data but slower
• Merge sort → good for large datasets
• Insertion sort → good for small or nearly sorted datasets 

Measuring Efficiency

Time Complexity

• Measures how execution time grows as input size increases 

Space Complexity

• Measures how much memory an algorithm uses 

Big O Notation

Big O describes the worst-case performance of an algorithm.

Common Complexities

Comparing Algorithm Complexity

• Lower Big O = more efficient 

For large datasets: 

• O(log n) is far better than O(n)
• O(n) is far better than O(n²) 

Example Comparison

• Linear search → O(n)
• Binary search → O(log n) 

Binary search is significantly faster for large datasets.

Algorithms for Data Structures

Stacks (LIFO)

• Operations: push, pop 

Used in: 

• Function calls
• Undo features 

Queues (FIFO)

• Operations: enqueue, dequeue 

Used in: 

• Task scheduling
• Buffers 

Linked Lists

• Nodes connected by pointers
• Efficient insertion/removal
• Sequential access only 

Trees

• Hierarchical structure 

Traversals:

Depth-First (Post-order) 

• Left → Right → Root 

Breadth-First 

• Level by level 

Searching Algorithms

Linear Search

• Checks each item in turn
• Works on unsorted data
• Time complexity: O(n) 

Binary Search

• Repeatedly halves the dataset
• Requires sorted data
• Time complexity: O(log n) 

Sorting Algorithms

Bubble Sort

• Repeatedly swaps adjacent elements
• Simple but inefficient
• Time complexity: O(n²) 

Insertion Sort

• Builds sorted list one item at a time
• Efficient for small/nearly sorted data
• Time complexity: O(n²) 

Merge Sort

• Divide and conquer
• Splits, sorts, merges
• Time complexity: O(n log n)
• Stable and efficient 

Quick Sort

• Uses a pivot to partition data
• Very fast on average
• Time complexity:
• Average: O(n log n)
• Worst: O(n²) 

Graph Algorithms

Dijkstra’s Algorithm

• Finds shortest path from a starting node
• Works on weighted graphs
• Always finds shortest path (no negative weights) 

A* Algorithm

• Uses heuristics to guide search
• Faster than Dijkstra in many cases 

Common in: 

• Navigation systems
• Video games 

Key Exam Tips

Always state time complexity when comparing algorithms 

Justify algorithm choice based on: 

• Data size
• Data structure
• Efficiency requirements 

Remember: 

• Sorting → improves searching efficiency
• Trade-off between time and space 

Summary

• Algorithms must be designed, analysed, and evaluated
• Efficiency is measured using Big O notation
• Different algorithms suit different data types and sizes
• Understanding standard algorithms is essential for solving real-world problems efficiently

Test your knowledge of this subject with this quiz.