B2.4.1 Describe the efficiency of specific algorithms by calculating their Big O notation to analyse their scalability.

📚 You can find additional information in the course companion pages 376 to 380. 

The Big Idea

As the size of the input grows, not all algorithms handle that growth equally. Big O notation is a formal way to describe how the time or space requirements of an algorithm scale with the size of the input (usually denoted n). This allows computer scientists and developers to compare algorithms not just by their correctness, but by their efficiency—which becomes especially critical for large-scale systems, high-performance computing, or real-time applications.

---

1. What Is Big O Notation?

Big O notation describes the upper bound of an algorithm’s growth rate in terms of time or space. It expresses the worst-case scenario performance, though other notations (e.g., Big Θ, Big Ω) are used for average or best cases.

It helps us answer the question:

"How does the number of operations (or memory usage) grow as the input size increases?"

Please understand this: 

Best case describes the scenario where the algorithm performs the fewest possible operations (e.g., searching for an item that is first in a list).
Average case estimates the algorithm’s performance across typical inputs, assuming a uniform or expected distribution of data.

These are often represented using different notations:

• Big Ω (Omega) for best case
• Big Θ (Theta) for average case
  But Big O focuses on the worst case, which is critical when analyzing performance guarantees.

---

Time Complexity

Time complexity measures the number of operations relative to input size.

Common Time Complexities (Big O)

Big O	Name	Example Algorithm / Operation	Growth Type & Example
O(1)	Constant	Accessing an element in an array by index (arr[5]); inserting/deleting from a hash table (average case).	The runtime does not depend on the input size. Example: no matter if the array has 10 items or 10 million, arr[5] still takes the same time.
O(log n)	Logarithmic	Binary search on a sorted array; finding an item in a balanced binary search tree.	The input size grows, but the number of steps increases very slowly. Example: searching through 1,000,000 items only takes about 20 steps.
O(n)	Linear	A single loop that checks each element once (e.g., finding the maximum value in an array).	Time increases directly in proportion to input size. Example: doubling the number of students doubles the time to check everyone’s grades.
O(n log n)	Linearithmic	Merge sort, quicksort (average case), heapsort.	Slightly slower than linear but still efficient for large inputs. Example: sorting 1,000 items takes ~10,000 steps.
O(n²)	Quadratic	Bubble sort, insertion sort, selection sort.	Time grows quickly: if you double the input size, runtime grows roughly fourfold. Example: sorting 10 items takes ~100 steps; sorting 100 items takes ~10,000.
O(2ⁿ)	Exponential	Recursive Fibonacci without memoization; brute-force subset generation.	Growth is extremely fast. Example: computing Fibonacci(50) can take billions of recursive calls.
O(n!)	Factorial	Generating all permutations of n elements; solving the Traveling Salesman Problem by brute force.	Growth is catastrophic: even n = 20 leads to ~2.4 quintillion operations. Practically impossible for large inputs.

---

2. Time Complexity

Time complexity describes how the number of operations grows relative to input size (n). It allows computer scientists to:

• Predict whether an algorithm will run efficiently as n increases.
• Compare algorithms beyond raw speed by looking at scalability.
• Identify when an algorithm is practical (e.g., O(n log n)) or impractical (e.g., O(2ⁿ)).

 

 

2. Time Complexity

Time complexity measures the number of operations relative to input size.

Example 1: Constant Time – O(1)

def get_first_element(arr):
    return arr[0]

• No matter how large arr is, it always takes the same time.

---

Example 2: Linear Time – O(n)

def print_all(arr):
    for item in arr:
        print(item)

• If the list has 10 elements → 10 operations
• If it has 1,000 elements → 1,000 operations

---

Example 3: Quadratic Time – O(n²)

def print_all_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

• For n = 100, runs 10,000 times
• Doubling n quadruples the work

---

3. Space Complexity

Space complexity measures how much memory is used, including:

• Input storage (sometimes excluded)
• Temporary variables
• Call stacks (for recursion)
• Auxiliary data structures

Example: Space-Efficient vs Space-Heavy

def sum_list(arr):
    total = 0        # O(1) space
    for item in arr:
        total += item
    return total

def make_copy(arr):
    return arr.copy()  # O(n) space

---

4. Calculating Big O

When analyzing a function’s complexity:

• Ignore constants: O(2n) becomes O(n)
• Focus on dominant term: O(n² + n) becomes O(n²)
• Separate independent inputs: O(n * m) if two loops depend on different inputs

---

Combined Example:

def example(arr):
    print(arr[0])               # O(1)
    for item in arr:            # O(n)
        print(item)
    for a in arr:               # O(n)
        for b in arr:           # O(n)
            print(a, b)         # O(n²)
# Total: O(1 + n + n²) → O(n²)

---

5. Scalability and Algorithm Choice

Why scalability matters:

An algorithm that works fine for 100 elements might be unusable for 1,000,000 elements.

Scenario 1: Searching a list of usernames

Algorithm	Complexity	Practical Limit
Linear Search	O(n)	Fine for small lists
Binary Search	O(log n)	Efficient for millions of items (requires sorted list)

Scenario 2: Sorting

Algorithm	Complexity	Notes
Bubble Sort	O(n²)	Inefficient, rarely used
Merge Sort	O(n log n)	Stable, reliable
Quick Sort	O(n log n) average, O(n²) worst	Fast but needs careful pivot selection

Scenario 3: Pathfinding in AI

Algorithm	Complexity	Use
Breadth-First Search	O(V + E)	Best for unweighted graphs
Dijkstra’s	O((V + E) log V)	Good for weighted graphs
A*	Depends on heuristic	Smart, scalable with good heuristics

---

6. Big O and Real-World Tradeoffs

Factor	Tradeoff Description
Speed vs memory	Some algorithms run fast but consume more memory (e.g., memoization)
Worst-case vs average-case	QuickSort is fast on average but slow in worst-case
Maintainability	Highly efficient algorithms can be harder to understand and maintain
Context matters	For small inputs, even O(n²) might be acceptable; for large-scale systems, O(n log n) or better is preferred

---

7. Summary Table

Concept	Description
Big O notation	Describes upper bound of algorithm performance as input grows
Time complexity	Number of operations performed as a function of input size
Space complexity	Amount of memory consumed relative to input
Scalability	How well an algorithm performs as input size increases
Efficient choice	Choosing the best algorithm depends on both theoretical performance and context (data size, memory limits, etc.)

---

Final Thoughts

Understanding Big O notation gives you the vocabulary and framework to talk about algorithm performance in precise, mathematical terms. It allows you to predict how your code will behave as the data grows and helps you choose the right tool for the job. Whether writing simple loops or implementing advanced algorithms, mastering complexity analysis is essential for becoming a proficient computer scientist or software engineer.