An Introduction to the Art of Computer Programming Using Python in the Age of Generative AI

XVII. Introduction to Algorithms and Efficiency

There should be one-- and preferably only one --obvious way to do it.
Tim Peters, Zen of Python

An algorithm is a set of clearly defined, logical steps to solve a particular problem or accomplish a task. In Python, algorithms are often expressed as functions, taking specific inputs and returning results after performing a sequence of operations. However, it’s not enough to just have a correct solution—understanding how efficient it is, especially as input sizes grow, is essential. Evaluating efficiency often involves time complexity and space complexity, both of which can be summarized using Big-O notation.

Big-O Notation

Big-O notation describes how an algorithm's runtime (or space requirement) scales as the input size increases. It focuses on the dominant factors that affect performance. By ignoring constant factors and lower-order terms, Big-O notation provides a high-level understanding of how an algorithm’s performance behaves in the worst-case scenario.

Common complexities include O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n). Each category reflects a different growth rate:

O(1) - Constant Time

An O(1) algorithm’s running time does not depend on the size of the input. That means it executes in effectively the same amount of time no matter how large (or small) the input is. 


fruits: list = ["apple", "banana", "orange"]

def get_first_element(fruits):
    if fruits:
        return fruits[0]
    else:
        return None

O(log n) - Logarithmic Time

An O(log n) algorithm grows more slowly than O(n). Typically, these algorithms reduce the problem size by a constant fraction at each step—common examples include binary search and searches on balanced trees. 


def binary_search(example_list, item):
    first = 0
    last = len(example_list) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if example_list[midpoint] == item:
            found = True
        else:
            if item < example_list[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

fruits = ["apple", "banana", "orange"]
item = "banana"
print(binary_search(fruits, item))

O(n) - Linear Time

An O(n) algorithm must process each element in the input at least once. This is common when examining or manipulating every item, such as summing or searching a list one element at a time. 


def sum_list(example_list):
    total = 0
    for element in example_list:
        total += element
    return total

numbers = [1,3,5,7]

print(sum_list(numbers))

O(n log n) - Linearithmic Time

Algorithms with O(n log n) complexity strike a balance between linear and quadratic growth. They often use a “divide and conquer” approach, repeatedly splitting data sets into smaller pieces and then merging or recombining them. Classic examples include mergesort and the average case of quicksort. 


def quicksort(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 quicksort(left) + middle + quicksort(right)

unsorted_list = [33, 10, 59, 26, -1, 2, 100]
sorted_list = quicksort(unsorted_list)
print(sorted_list)

In this example, each recursive call divides the list into sublists based on a chosen pivot. Over multiple recursive splits, the average time complexity is O(n log n). However, selecting a poor pivot in certain cases can degrade performance to O(n2), which is why randomized pivot selection or other optimizations are often used.

O(n^2) - Quadratic Time

In O(n^2) algorithms, an operation is repeated for each element in the input list, resulting in nested loops. Sorting methods like bubble sort or insertion sort can exhibit quadratic behavior, making them slow for large datasets. 


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

unordered_numbers = [55, 2, -23, 6, 24]

print(bubble_sort(unordered_numbers))

O(2^n) - Exponential Time

O(2^n) algorithms have runtimes that grow exponentially with input size. Solutions to complex combinatorial problems or brute-force searches (for instance, the naive Fibonacci implementation or the traveling salesperson problem) can fall into this category. 


def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))

Considering Space Complexity

Alongside time complexity, space complexity measures how much additional memory (or other storage) an algorithm requires relative to the input size. Similar to time complexity, we use Big-O notation for space. Some examples:

For instance, mergesort requires O(n) additional space to merge the sorted sublists, while bubble sort requires only O(1) extra space because it sorts in-place. Understanding space requirements is crucial for large inputs or memory-limited environments, ensuring that an algorithm’s memory usage remains feasible as input sizes grow.

Prompting Generative AI for Efficient Code and Algorithms

When seeking help from a generative AI model, frame your questions to focus on the purpose and constraints of your algorithm. Instead of asking, “How do I sort a list?”, you could specify: “How can I implement a bubble sorting algorithm to sort a list of integers in Python?” to receive more targeted code examples.

Also, provide extra context—like data size, concerns about worst-case performance, or whether you need in-place sorting. For example, “I have a list of integers that may contain duplicates. What is an efficient method to sort this list in Python using bubble sort, and how does it compare to merge sort in terms of complexity?”

Example Prompt:
Write a functional program for merge sort, including functions to split the list and merge sorted sublists.

Resulting AI-generated code:


def merge_sort(lst):
    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):
    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

unordered_numbers = [55, 2, -23, 6, 24]
sorted_numbers = merge_sort(unordered_numbers)
print(sorted_numbers)
Back to Home