OCR A Level CS 2.3.1 Analysis, Design and Comparison of Algorithms

What are the two main factors in algorithm analysis?

Time complexity (execution time) and space complexity (memory usage).

What is time complexity?

The time an algorithm takes to execute, based on input size.

What is space complexity?

The amount of memory an algorithm requires to run.

What is Big-O notation?

A way to express the worst-case growth rate of an algorithm.

Big-O notation with its description:

Big-O Notation	Description
O(1)	Constant time – does not depend on input size
O(n)	Linear time – grows proportionally to input size
O(n²)	Quadratic time – grows with the square of input size
O(2ⁿ)	Exponential time – doubles with each additional input
O(log n)	Logarithmic time – increases slowly even with large inputs

Which Big-O notation is the best for performance?

O(1) (Constant time), followed by O(log n) (Logarithmic time).

Which Big-O notation is considered inefficient?

O(2ⁿ) (Exponential time) as it grows too fast.

Give an example of O(1) constant time.

A program that prints "Hello" – it always takes the same time.

Give an example of O(n) linear time.

A loop that iterates through an entire list once.

Give an example of O(n²) quadratic time.

A nested loop that checks every pair in a list.

What kind of algorithm has O(log n) logarithmic time?

Binary search, where the input size is halved each step.

What should be considered when designing an algorithm?

✅ Efficiency (time & space complexity)
✅ Scalability (performance as input grows)
✅ Correctness (produces expected results)
✅ Readability (clear, maintainable code)

What is linear search, and what is its Big-O notation?

Searches each item one by one → O(n) (Linear time).

What is binary search, and what is its Big-O notation?

Divides the list in half each step (requires sorting) → O(log n) (Logarithmic time).

Which is faster: linear or binary search?

Binary search (O(log n)) is much faster for large lists.

What is bubble sort, and what is its Big-O notation?

Repeatedly swaps adjacent elements → O(n²) (Quadratic time).

Why is bubble sort inefficient?

It makes too many comparisons and swaps for large lists.