??Big O Notation and Python: A Practical Guide for CS Students

Hey all,

In this article, we’ll explore Big O notation with practical Python examples.

Whether you’re preparing for technical interviews or learning for the first time, this guide will help you brush up on the fundamentals and solidify your understanding.

What Is Big O Notation?

Big O notation is like a way to measure how fast or slow, and how much memory an algorithm takes, depending on how many inputs there are.

It’s about scalability. How does your code perform as the dataset increases?

Some common Big O complexities include:

• O(1): Constant time
• O(n): Linear time
• O(n2): Quadratic time
• O(log n): Logarithmic time
• O(n log n): Log-linear time

?? ??Let’s look at some examples for each use case. I’ll be using Python for readability.

1. Constant Time: O(1)

An algorithm that doesn’t depend on the size of the input runs in constant time.

def get_first_element(arr):
    return arr[0]

# Example:
nums = [10, 20, 30, 40]
print(get_first_element(nums))   # Always O(1), regardless of array size        

Use Case: Accessing an element in a dictionary or list by index.

2. Linear Time: O(n)

Algorithms that iterate through the entire dataset exhibit linear time complexity.

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

# Example:
nums = [10, 20, 30, 40]
print(find_max(nums))  # O(n), scales with array size        

Use Case: Searching through a list

3. Quadratic Time: O(n2)

Nested loops often result in quadratic time complexity.

def print_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(f"Pair: ({arr[i]}, {arr[j]})")

# Example:
nums = [1, 2, 3]
print_pairs(nums)  # O(n2), grows exponentially with input size        

Use Case: Comparing all pairs in a dataset (e.g., brute-force algorithms)

4. Logarithmic Time: O(log n)

Efficient algorithms like binary search reduce the problem size at each step

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

# Example:
nums = [10, 20, 30, 40, 50]
print(binary_search(nums, 30))  # O(log n)        

Use Case: Searching in sorted datasets

5. Log-Linear Time: O(n log n)

Sorting algorithms like merge sort exhibit log-linear complexity

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# Example:
nums = [38, 27, 43, 3, 9, 82, 10]
merge_sort(nums)  # O(n log n)        

Use Case: Sorting large datasets

Conclusion

By analysing the complexity of your algorithms, you can be sure your code scales well and performs efficiently, whether you’re coding a personal project or working on something new at work.

What would you like me to talk about next? Leave a comment and let me know!

Yours,

Hanisa ??