Efficient Python Algorithms Explained

Python algorithm code with Big O notation on a dark editor background

Algorithm Efficiency in Python

Writing code that runs correctly is the first step. Writing code that scales is the second. Algorithm efficiency measures how well a solution performs as input size grows, expressed across two dimensions: time and space.

Time complexity describes how an algorithm's runtime scales with input size. Big O notation captures the upper bound. An algorithm with O(n) time takes twice as long when the input doubles; one with O(1) time takes the same amount of time regardless. Choosing the wrong time complexity at scale is the most common source of performance bugs in production Python.

Space complexity measures memory usage relative to input size, also expressed in Big O. Lower space complexity matters when working with large datasets or memory-constrained environments.

Understanding both lets you choose the right algorithm before writing a line of code, rather than profiling it after the fact.

Sorting Algorithms

Python's built-in sort() uses Timsort (O(n log n), stable), but knowing the classic algorithms is essential for assignments and interviews. Here are 5 sorting algorithms with implementations and complexity analysis.

1. Bubble Sort steps through the list, compares adjacent elements, and swaps them when out of order. Time complexity: O(n^2). Practical for small datasets or teaching, not for production.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. Selection Sort splits the list into a sorted and unsorted region, then repeatedly moves the minimum from the unsorted region to the sorted one. Time complexity: O(n^2). No advantage over bubble sort for large inputs.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3. Insertion Sort builds the sorted list one element at a time, inserting each new element into its correct position. Time complexity: O(n^2) worst case, O(n) on nearly-sorted lists. Efficient for small or nearly-sorted inputs.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

4. Merge Sort is a divide-and-conquer algorithm: split the list in half, sort each half recursively, then merge. Time complexity: O(n log n). More efficient than the O(n^2) algorithms above for larger datasets.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    return result + left + right

5. Quick Sort picks a pivot, partitions the list into elements less than and greater than the pivot, then sorts each partition recursively. Average time complexity: O(n log n). Worst case: O(n^2) when the pivot is consistently the smallest or largest element.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

Comparison: Bubble, selection, and insertion sort are O(n^2) and impractical for large inputs. Merge sort and quick sort are both O(n log n) average case; quick sort is often faster in practice due to better cache behavior, but merge sort is preferred when stability matters.

Searching Algorithms

3 searching algorithms cover the vast majority of interview and assignment problems.

1. Linear Search checks each element sequentially. Time complexity: O(n). Use it when the list is unsorted or small.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

2. Binary Search requires a sorted list and halves the search interval on each step. Time complexity: O(log n). Significantly faster than linear search for large sorted datasets.

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

3. Hash Tables provide O(1) average-case lookup by mapping keys to array indices through a hash function. Use them when fast retrieval is critical, such as in dictionary implementations or database index simulations.

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def insert(self, key, value):
        index = hash(key) % self.size
        self.table[index].append((key, value))

    def search(self, key):
        index = hash(key) % self.size
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

Data Structures for Efficient Operations

The right data structure determines whether a common operation costs O(1) or O(n). Here are 6 core Python structures with their complexity profiles.

1. Lists store elements in order. Accessing by index: O(1). Appending to the end: O(1) amortized. Inserting or deleting in the middle: O(n) because elements must shift.

my_list = [1, 2, 3, 4, 5]
print(my_list[0])   # O(1) access
my_list.append(6)   # O(1) amortized
my_list.pop(0)      # O(n): shifts all elements

2. Arrays (from the array module) are like lists but fixed-type and more memory-efficient. Random access: O(1). Mid-list insert or delete: O(n).

import array
my_array = array.array('i', [1, 2, 3, 4, 5])
print(my_array[0])      # O(1)
my_array.insert(0, 0)   # O(n)
my_array.pop()          # O(1)

3. Sets are unordered collections of unique elements. Membership test, insert, and delete: all O(1) average.

my_set = {1, 2, 3, 4, 5}
print(1 in my_set)  # O(1)
my_set.add(6)       # O(1)
my_set.remove(1)    # O(1)

4. Dictionaries map keys to values. Lookup, insert, and delete: O(1) average. The standard Python dict preserves insertion order since Python 3.7.

my_dict = {'a': 1, 'b': 2, 'c': 3}
print(my_dict['a'])  # O(1)
my_dict['d'] = 4     # O(1)
del my_dict['b']     # O(1)

5. Linked Lists chain nodes together, each holding data and a reference to the next node. Insert or delete at the head: O(1). Searching for an element: O(n).

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete_at_beginning(self):
        if self.head:
            self.head = self.head.next

6. Trees are hierarchical structures where nodes connect through parent-child edges. A binary search tree (BST) supports insert, delete, and search in O(log n) average when balanced.

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, root, data):
        if not root:
            return TreeNode(data)
        if data < root.data:
            root.left = self._insert(root.left, data)
        elif data > root.data:
            root.right = self._insert(root.right, data)
        return root

Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping subproblems, storing each result to avoid recalculating it. Two techniques apply: memoization (top-down, cache results as you recurse) and bottom-up iteration (solve the smallest subproblems first, build toward the answer).

The Fibonacci sequence illustrates the gap. A naive recursive solution recalculates fib(n-2) repeatedly, giving O(2^n) time. Memoization reduces it to O(n).

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55

The 0/1 knapsack problem shows bottom-up DP. Given items with weights and values and a knapsack with fixed capacity, find the maximum value you can carry. The brute-force approach is O(2^n); DP solves it in O(n * capacity).

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                )
            else:
                dp[i][w] = dp[i - 1][w]
    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # Output: 7

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step. They are fast and simple, but they do not always reach the global optimum. Apply them when the problem has the "greedy choice property": local optima combine into a global optimum.

The fractional knapsack problem is one case where greedy works. Sort items by value-to-weight ratio, then fill the knapsack starting with the highest-ratio item.

def fractional_knapsack(values, weights, capacity):
    value_per_weight = [(v / w, w) for v, w in zip(values, weights)]
    value_per_weight.sort(reverse=True)
    total_value = 0
    for vpw, w in value_per_weight:
        if capacity >= w:
            total_value += vpw * w
            capacity -= w
        else:
            total_value += vpw * capacity
            break
    return total_value

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))  # Output: 240.0

The activity selection problem is another. Given activities with start and finish times, select the maximum number of non-overlapping activities. Sort by finish time and greedily pick each activity that starts after the previous one finishes.

def activity_selection(start, finish):
    n = len(start)
    activities = [(finish[i], start[i]) for i in range(n)]
    activities.sort()
    selected_activities = []
    prev_finish = 0
    for f, s in activities:
        if s >= prev_finish:
            selected_activities.append((s, f))
            prev_finish = f
    return selected_activities

start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish))  # Output: [(1, 2), (3, 4), (5, 7), (8, 9)]

Note: for the 0/1 knapsack (where items cannot be split), greedy fails. That is why the dynamic programming solution above is necessary.

String Manipulation Algorithms

String algorithms handle text processing, pattern matching, and sequence comparison. Here are 3 categories with Python implementations.

Pattern matching finds occurrences of a pattern inside a text. Three algorithms cover the spectrum:

Brute force: check every position in the text. Time complexity: O(m * n) where m is the pattern length and n is the text length.
Rabin-Karp: uses hashing to compare the pattern against substrings. Average time: O(n + m). Worst case: O(n * m) on hash collisions.
Knuth-Morris-Pratt (KMP): precomputes a failure function to skip redundant comparisons. Time complexity: O(n + m) guaranteed.

Longest Common Subsequence (LCS): finds the longest subsequence shared by two strings. Dynamic programming solves it in O(m * n) where m and n are the string lengths.

Edit distance: counts the minimum number of insertions, deletions, or substitutions to transform one string into another. Also O(m * n) via dynamic programming.

# Brute force pattern matching
def brute_force_pattern_matching(text, pattern):
    occurrences = []
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:
            occurrences.append(i)
    return occurrences

# Rabin-Karp pattern matching
def rabin_karp_pattern_matching(text, pattern):
    occurrences = []
    n, m = len(text), len(pattern)
    pattern_hash = hash(pattern)
    for i in range(n - m + 1):
        if hash(text[i:i + m]) == pattern_hash:
            if text[i:i + m] == pattern:
                occurrences.append(i)
    return occurrences

# KMP pattern matching
def kmp_pattern_matching(text, pattern):
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        j = 0
        for i in range(1, len(pattern)):
            while j > 0 and pattern[i] != pattern[j]:
                j = lps[j - 1]
            if pattern[i] == pattern[j]:
                j += 1
            lps[i] = j
        return lps

    occurrences = []
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j - 1]
        if text[i] == pattern[j]:
            if j == m - 1:
                occurrences.append(i - m + 1)
                j = lps[j]
            else:
                j += 1
    return occurrences

Numerical Algorithms

3 numerical algorithms appear regularly in Python assignments: GCD via Euclid, prime generation via the Sieve of Eratosthenes, and fast exponentiation.

Euclidean GCD finds the greatest common divisor of two integers by repeated modulo. Time complexity: O(log(min(a, b))).

def euclidean_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Sieve of Eratosthenes generates all primes up to n by iteratively marking multiples of each prime as composite. Time complexity: O(n log log n).

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return [i for i in range(n + 1) if primes[i]]

Fast exponentiation computes base ** exponent in O(log n) by squaring on even exponents instead of multiplying n times.

def fast_exponentiation(base, exponent):
    if exponent == 0:
        return 1
    elif exponent % 2 == 0:
        result = fast_exponentiation(base, exponent // 2)
        return result * result
    else:
        result = fast_exponentiation(base, (exponent - 1) // 2)
        return base * result * result

These algorithms cover the problems that appear most frequently in Python coursework: sorting and searching account for most autograder test cases, dynamic programming shows up in optimization assignments, and string algorithms appear in NLP and compiler projects. If an assignment is giving you trouble, Python assignment help from developers who write production Python is available from $29, with 50% paid upfront and the rest after you verify the code runs.

For more algorithm coverage across languages, see Traversal Algorithms in Java and Python with Code and Different Sorting Algorithms in Java and Step by Step Implementation.