Understanding Big O Notation in Python

Introduction

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it’s used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Common Big O Notations

O(1) - Constant Time

Operations that always take the same amount of time, regardless of input size.

def get_first_item(lst):
    """O(1) - constant time operation"""
    return lst[0] if lst else None

def is_empty(lst):
    """O(1) - checking length is constant time"""
    return len(lst) == 0

O(n) - Linear Time

Operations whose time scales linearly with input size.

def find_element(lst, target):
    """O(n) - linear time as we might need to check every element"""
    for item in lst:
        if item == target:
            return True
    return False

def sum_list(lst):
    """O(n) - must visit each element once"""
    total = 0
    for num in lst:
        total += num
    return total

O(n²) - Quadratic Time

Operations whose time scales with the square of the input size.

def bubble_sort(lst):
    """O(n²) - nested loops over the list"""
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst

def find_duplicates(lst):
    """O(n²) - comparing each element with every other element"""
    duplicates = []
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j] and lst[i] not in duplicates:
                duplicates.append(lst[i])
    return duplicates

O(log n) - Logarithmic Time

Operations whose time scales logarithmically with input size.

def binary_search(lst, target):
    """O(log n) - divides search space in half each time"""
    left, right = 0, len(lst) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

O(n log n) - Linearithmic Time

Common in efficient sorting algorithms.

def merge_sort(lst):
    """O(n log n) - efficient sorting algorithm"""
    if len(lst) <= 1:
        return lst
    
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    
    return merge(left, right)

def merge(left, right):
    """Helper function for merge sort"""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Space Complexity Examples

O(1) Space Complexity

Operations that use a constant amount of extra space.

def find_max(lst):
    """O(1) space - only uses one variable regardless of input size"""
    if not lst:
        return None
    max_val = lst[0]
    for num in lst:
        if num > max_val:
            max_val = num
    return max_val

O(n) Space Complexity

Operations that use extra space proportional to input size.

def create_double_list(lst):
    """O(n) space - creates new list of same size as input"""
    return [x * 2 for x in lst]

Common Operations Time Complexity

Lists

# List operations and their time complexity
lst = [1, 2, 3, 4, 5]

# O(1)
lst.append(6)       # Add to end
lst.pop()          # Remove from end
lst[0]             # Access by index

# O(n)
lst.insert(0, 0)   # Insert at beginning
lst.pop(0)         # Remove from beginning
lst.index(3)       # Find element
3 in lst          # Check existence

Dictionaries

# Dictionary operations and their time complexity
d = {'a': 1, 'b': 2}

# O(1) average case
d['c'] = 3         # Add/update item
value = d['a']     # Get item
del d['b']         # Delete item
'c' in d           # Check existence

# O(n)
list(d.keys())     # Get all keys
d.copy()           # Create shallow copy

Best Practices

1. Choose appropriate data structures:

   • Use lists for ordered data with frequent access by index
   • Use dictionaries for key-value pairs with frequent lookups
   • Use sets for unique elements with frequent membership testing

2. Optimize for common operations:

   • If you need frequent insertions/deletions at the beginning, consider using collections.deque
   • If you need to maintain a sorted sequence, consider using bisect module
   • If you need to count elements, use collections.Counter

3. Avoid nested loops when possible:

   • Use hash tables (dictionaries) for lookups instead of nested searches
   • Use set operations for intersection/union instead of nested loops

Common Pitfalls

1. Hidden loops in list operations:

# This looks like O(1) but is actually O(n)
lst = [1, 2, 3, 4, 5]
lst.insert(0, 0)  # Shifts all elements right

# This looks like O(n) but is O(n²)
lst = lst + [6]   # Creates new list and copies all elements

2. String concatenation in loops:

# Bad: O(n²) time complexity
result = ""
for i in range(n):
    result += str(i)

# Better: O(n) time complexity
result = "".join(str(i) for i in range(n))

3. Unnecessary space usage:

# Bad: O(n) extra space
def sum_even(lst):
    evens = [x for x in lst if x % 2 == 0]
    return sum(evens)

# Better: O(1) extra space
def sum_even(lst):
    return sum(x for x in lst if x % 2 == 0)

Interview angle

• “What does Big-O actually describe?” - asymptotic growth of the worst case, ignoring constants. It says how the cost scales, not how fast it runs, which is why an O(n log n) algorithm can lose to an O(n^2) one on small inputs.
• “What are the complexities of Python’s built-ins?” - list index and append O(1), insert and delete at the front O(n); dict and set lookup O(1) average; in on a list O(n) but on a set O(1). The list-versus-set membership difference is the single most common real-world fix.
• “Amortised versus average case?” - amortised is the average over a sequence of operations, guaranteed by the algorithm - list append is amortised O(1) because occasional resizes are spread across many cheap appends. Average case depends on input distribution.
• “When does complexity analysis mislead?” - when constants or memory access patterns dominate, which is common at realistic input sizes. Profile before optimising; asymptotics tell you what will eventually matter, not what currently does.