Understanding BIG O Calculations

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

1. Basic Idea

2. Common Time Complexities

big_o_graph_annotated.png

In order of least dominating term O(1) to most dominating term (the one that grows the fastest)

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

5. Space Complexity

6. Visualizing Growth Rates

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

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:

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:

  1. Add the complexities for sequential parts.

  2. Multiply the complexities for nested parts.

  3. Drop the lower-order terms and constant factors.

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

Examples:

def combined_example(arr):
    # Sequential part: Loop that processes each element.
    # This loop runs O(n) times.
    for x in arr:
        print(x)  # O(1) operation per element.

    # Nested part: For each element in arr, loop over arr again.
    # The inner loop is nested within the outer loop, giving O(n) * O(n) = O(n²) operations.
    for x in arr:
        for y in arr:
            print(x, y)  # O(1) operation per inner loop iteration.

# If we call combined_example, the overall complexity is:
# O(n) [from the first loop] + O(n²) [from the nested loops].
# For large n, O(n²) dominates O(n), so we drop the lower-order term and constant factors,
# and the overall time complexity is O(n²).

if __name__ == "__main__":
    sample_list = [1, 2, 3, 4, 5]
    combined_example(sample_list)
# Binary search on a sorted list
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Outer loop processes each query, each using binary search
def search_all(sorted_arr, queries):
    results = []
    for query in queries:         # O(n) if queries contains n items
        index = binary_search(sorted_arr, query)  # O(log n)
        results.append(index)
    return results

if __name__ == '__main__':
    # Assume this list is already sorted
    sorted_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    # List of queries (if its size is roughly n, overall complexity is O(n log n))
    queries = [3, 7, 10]
    print("Search results:", search_all(sorted_arr, queries))

This example demonstrates how nested operations (a loop with an inner binary search) yield an O(n log n) algorithm.

Special Note: If using python sort method, it uses TimSort which worse case is O(n log n)


Revision #9
Created 28 December 2024 00:35:36 by victor
Updated 26 March 2025 00:32:08 by victor