Algorithm Efficiency using Big O Notation

Overview

Big O Notation is a mathematical way to describe the efficiency of an algorithm, focusing on how the algorithm's performance scales with the size of the input. It helps in comparing different algorithms by providing a high-level understanding of their time and space requirements, particularly as the input size grows.

What is Big O Notation?

• Big O notation expresses the upper bound of an algorithm's growth rate, describing its worst-case scenario performance.
• It measures:
  • Time Complexity: How execution time increases with input size.
  • Space Complexity: How memory usage increases with input size.

Common Big O Complexities

Complexity	Notation	Description	Example Algorithm
Constant	O(1)	Performance is unaffected by input size.	Accessing an array element.
Logarithmic	O(log n)	Performance grows logarithmically as input size increases.	Binary search.
Linear	O(n)	Performance grows linearly with input size.	Linear search.
Polynomial	O(n²), O(n³), etc.	Performance grows polynomially with input size.	Bubble sort (O(n²)).
Exponential	O(2ⁿ)	Performance doubles with each additional input element.	Recursive Fibonacci.

Interpreting and Recognising Big O on Graphs

Each Big O notation has a distinct shape when graphed (Input size on the x-axis and Time on the y-axis):

1. Constant Complexity (O(1)): A flat line—performance does not change with input size.

2. Logarithmic Complexity (O(log n)): A curve that rises quickly at first but flattens as the input grows.

3. Linear Complexity (O(n)): A straight line with a constant slope.

4. Polynomial Complexity (O(n²)): A parabolic curve—steeper growth than linear.

5. Exponential Complexity (O(2ⁿ)): A sharply rising curve—rapid growth as input increases.

Graph of Complexities

Below is an approximate visualisation of how different complexities grow:

|                  *
|              *        (O(2ⁿ) - Exponential)
|          *
|      *
|   *
|  *               (O(n²) - Polynomial)
|*
|                   (O(n) - Linear)
|
|                 (O(log n) - Logarithmic)
|
|  *  *  *  *  *  (O(1) - Constant)
----------------------------------------------------
       Input Size (n)

Examples of Big O Analysis

How to Determine Big O Complexity

1. Identify Loops:

• A single loop running n times is O(n).
• A nested loop (loop within a loop) over n is O(n²).

2. Examine Recursive Calls:

• If each recursive call splits the problem in half (like binary search), it's O(log n).
• If recursion branches exponentially, it's O(2ⁿ).

3. Simplify:

• Drop lower-order terms and constants.
• For example: If an algorithm runs in n + log n time, it simplifies to O(n).

Note Summary