Skip to main content

BIG O Notation and Calculation

Big O notation is a way to describe how the algorithm grow as the input size increases. Two things it considers: 

  • Runtime
  • Space 

1. Basic Idea

  • What It Measures:
    Big O notation focuses on the worst-case scenario of an algorithm’s performance. It tells you how the running time (or space) increases as the size of the input grows.

  • Ignoring Constants:
    It abstracts away constants and less significant terms. For instance, if an algorithm takes 3n + 5 steps, it’s considered O(n) because, for large n, the constant 5 and multiplier 3 become negligible compared to n.

2. Common Time Complexities

  • O(1) – Constant Time:
    The runtime does not change with the size of the input.

    • Example: Accessing an element in a list by its index.

  • O(n) – Linear Time:
    The runtime increases linearly with the input size.

    • Example: Iterating through all elements of an array to find a specific value.

  • O(n²) – Quadratic Time:
    The runtime increases quadratically as the input size increases.

    • Example: Using two nested loops to compare all pairs in an array.

  • O(log n) – Logarithmic Time:
    The runtime increases slowly as the input size increases.

    • Example: Binary search in a sorted list.

  • O(n log n):
    Often seen in efficient sorting algorithms like mergesort or heapsort.

    • Example: Sort the list in O(n), then use a Binary search in a sorted list O(logn).

3. Understanding Through Examples

Constant Time – O(1)

def get_first_element(lst):
    return lst[0]  

Regardless of list size, only one operation is performed.

Linear Time – O(n)

def find_max(lst):
    max_val = lst[0]
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

In the find_max function, every element is inspected once, so the time grows linearly with the list size.

Quadratic Time – O(n²)

def print_all_pairs(lst):
    for i in range(len(lst)):
        for j in range(len(lst)):
            print(lst[i], lst[j])

Here, for each element, you’re iterating over the entire list, leading to a quadratic number of comparisons.

4. Why Big O Matters

  • Performance Insight:
    Understanding Big O helps you predict how your solution will scale.

    • O(n) solution will generally perform better than an O(n²) solution as the input size increases.

  • Algorithm Choice:
    It allows you to compare different algorithms and select the most efficient one for your needs. 

    • Discussing Big O can show your understanding of algorithm efficiency.

5. Space Complexity

  • Just as you can analyze time complexity, Big O also helps you understand how much memory an algorithm requires relative to the input size.

6. Visualizing Growth Rates

Imagine a graph where the x-axis is the input size and the y-axis is the time taken:

  • O(1) is a flat line.

  • O(n) is a straight, upward-sloping line.

  • O(n²) starts off similar for small inputs but grows much faster as n increases.

7. Combining big-o

When you have different parts of an algorithm with their own complexities, combining them depends on whether they run sequentially or are nested within each other.

1. Sequential Operations

If you perform one operation after the other, you add their complexities. For example, if one part of your code is O(n) and another is O(n²), then the total time is:

  • O(n) + O(n²) = O(n²)

This is because, as n grows, the O(n²) term dominates and the lower-order O(n) becomes negligible.

def sequential_example(nums):
    # First part: O(n)
    for num in nums:
        print(num)

    # Second part: O(n²)
    for i in range(len(nums)):
        for j in range(len(nums)):
            print(nums[i], nums[j])

Here, the overall time complexity is O(n) + O(n²), which simplifies to O(n²).

2. Nested Operations

If one operation is inside another (nested loops), you multiply their complexities. For example, if you have an outer loop that runs O(n) times and an inner loop that runs O(n) times for each iteration, then the total time is:

def nested_example(nums):
    for i in range(len(nums)):          # O(n)
        for j in range(len(nums)):      # O(n) for each i
            print(nums[i], nums[j])
This nested structure gives you O(n²) overall.

3. Combining Different Parts

In real problems, your code might have a mix of sequential and nested parts. The key idea is:

  • Add the complexities for sequential parts.

  • Multiply the complexities for nested parts.

  • Drop the lower-order terms and constant factors.

Quick Rule:
When adding complexities, the dominating term (the one that grows the fastest) is the one that determines the overall Big O notation.