07. Big O in Everyday Code

Determining the Big O efficiency of code is the crucial first step in optimization. Understanding the Big O category of an algorithm allows you to make a judgment call: a slow category like $O(N^2)$ should signal a pause to investigate faster alternatives, even if an $O(N^2)$ solution is the best available for a given problem.

Mean Average of Even Numbers

Here is a method that accepts an array of numbers and returns the mean average of all its even numbers:

def average_of_even_numbers(array):
    sum = 0
    count_of_even_numbers = 0
    for number in array:
        if number % 2 == 0:
            sum += number
            count_of_even_numbers += 1
    if count_of_even_numbers == 0:
        return None
    return sum // count_of_even_numbers

Big O Efficiency Analysis

1. Determine N: The $N$ data elements are the values in the input array. $N$ is the size of the array.
2. Analyze Steps (Worst-Case):
   • The core of the algorithm is the for loop that iterates over each of the $N$ elements. This means the algorithm takes at least $N$ steps.
   • We analyze the steps inside the loop for the worst-case scenario, which is when all the numbers in the array are even.
     • For every number, there is one comparison (if number % 2 == 0).
     • If the number is even (worst case), there are two more steps: modifying sum and modifying count_of_even_numbers.
     • Total steps inside the loop in the worst case: $1+2=3$ steps per element.
     • Total steps from the loop: $3N$.
3. Account for Constant Steps:
   • Before the loop: Two steps to initialize sum and count_of_even_numbers to 0.
   • After the loop: One step for the final division calculation (return sum // count_of_even_numbers).
   • Total constant steps: $2+1=3$.
   • Total overall steps: $3N+3$.
4. Apply Big O Rules:
   • We drop constant numbers (the 3s).
   • The efficiency is expressed as $O(N)$.

The time complexity of the average_of_even_numbers method is $O(N)$ (linear time).

Word Builder

Two-Character strings

The first algorithm is designed to collect every combination of two-character strings from an input array of single characters (e.g., ["a", "b", "c", "d"] $\to$ ['ab', 'ac', 'ad', 'ba', 'bc', 'bd', 'ca', 'cb', 'cd', 'da', 'db', 'dc']):

def word_builder(array):
    collection = []
    for index_i, i in enumerate(array):
        for index_j, j in enumerate(array):
            if index_i != index_j:
                collection.append(i + j)
    return collection

Time complexity Analysis (Two Nested Loops)

1. Determine N: $N$ is the number of items (characters) in the input array.
2. Analyze Steps:
   • The outer loop (for i) iterates over all $N$ elements.
   • For each iteration of the outer loop, the inner loop (for j) also iterates over all $N$ elements.
   • Total steps are $N$ steps multiplied by $N$ steps, resulting in $N^2$ iterations.

This is the classic case of nested loops, and its efficiency is $O(N^2)$ (quadratic time).

Three-Character strings

If we modify the algorithm to compute combinations of three-character strings, the implementation requires three nested loops:

def word_builder(array):
    collection = []
    for index_i, i in enumerate(array):
        for index_j, j in enumerate(array):
            for index_k, k in enumerate(array):
                if (index_i != index_j and
                    index_j != index_k and index_i != index_k):
                    collection.append(i + j + k)
    return collection

Time Complexity Analysis (Three Nested Loops)

• For $N$ data elements, the steps are $N$ (loop $i$) multiplied by $N$ (loop $j$) multiplied by $N$ (loop $k$).
• Total steps are $N\times N\times N=N^3$.

The time complexity of this algorithm is $O(N^3)$ (cubic time).

If there were four or five nested loops, the complexity would be $O(N^4)$ or $O(N^5)$, respectively. On a graph, these complexities curve sharply upward, making them significantly slower than $O(N^2)$ as $N$ grows . Optimizing code from $O(N^3)$ to $O(N^2)$ would result in an exponentially faster execution.

Array Sample

The goal of this function is to take a small sample (the first, middle, and last values) from an array, which we expect to be very large.

def sample(array):
    if not array:
        return None
    first = array[0]
    middle = array[len(array) // 2]
    last = array[-1]
    return [first, middle, last]

Big O Efficiency Analysis

1. Determine N: $N$ is the number of elements in the input array.
2. Analyze Steps: We need to determine how the number of steps changes as $N$ increases.
   • Checking for empty array: One step.
   • Accessing array[0] (first element): One step.
   • Finding length and calculating middle index: One step (calculating array length, dividing by 2, and performing integer division are all constant time operations).
   • Accessing array[len(array) // 2] (middle element): One step.
   • Accessing array[-1] (last element): One step.
   • Returning the final list: One step.

The total number of steps is a fixed, constant number (approximately 6 steps), regardless of whether the array has 10 elements or one million elements. Since the number of steps remains constant no matter the size of $N$, this algorithm is considered $O(1)$. This is known as constant time efficiency.

Average Celsius Reading

The function average_celsius takes an array of Fahrenheit readings, converts them to Celsius, and calculates the mean average.

def average_celsius(fahrenheit_readings):
    if not fahrenheit_readings:
        return None
    celsius_numbers = []
    # Loop 1: Convert each reading to Celsius and append to array:
    for fahrenheit_reading in fahrenheit_readings:
        celsius_conversion = (fahrenheit_reading - 32) / 1.8
        celsius_numbers.append(celsius_conversion)
 
    # Loop 2: Calculate average:
    sum = 0
    for celsius_number in celsius_numbers:
        sum += celsius_number
    return sum // len(celsius_numbers)

Big O Efficiency Analysis

1. Determine N: $N$ is the number of elements in the input array fahrenheit_readings.
2. Analyze Steps:
   • Loop 1 (Conversion): This loop iterates over every one of the $N$ readings once. This results in $N$ steps.
   • Loop 2 (Summation): This loop iterates over every one of the $N$ converted Celsius numbers once. This also results in $N$ steps.

Since the loops are executed sequentially (one after the other), the total steps are $N$ steps $+N$ steps, which equals $2N$ (plus a few constant steps for initialization/return). Because Big O notation drops constants, the efficiency of this algorithm is $O(N)$.

This is an example of two sequential loops resulting in $O(N)$, not $O(N^2)$, because they are added ($N+N=2N$) and not nested ($N\times N=N^2$).

Clothing Labels

The function mark_inventory creates text for clothing labels by combining each item in an array with sizes 1 through 5. For example, if we have the array, ["Purple Shirt", "Green Shirt"], we want to produce label text for those shirts like this: ["Purple Shirt Size: 1", "Purple Shirt Size: 2", "Purple Shirt Size: 3", "Purple Shirt Size: 4", "Purple Shirt Size: 5", "Green Shirt Size: 1", "Green Shirt Size: 2", "Green Shirt Size: 3", "Green Shirt Size: 4", "Green Shirt Size: 5"].

def mark_inventory(clothing_items):
    clothing_options = []
    for item in clothing_items: # Outer Loop
        for size in range(1, 6): # Inner Loop
            clothing_options.append(item + " Size: " + str(size))
    return clothing_options

Big O Efficiency Analysis

1. Determine N: $N$ is the size of the input array clothing_items.
2. Analyze Steps: This code contains nested loops, but they do not lead to $O(N^2)$.
   • Outer Loop: Iterates over all $N$ items.
   • Inner Loop: Iterates a constant five times (for sizes 1 through 5), regardless of the size of $N$.

The total number of steps is $N\times 5=5N$. Since Big O notation ignores constants (the 5), the efficiency of this algorithm is also $O(N)$ (linear time).

Count the Ones

The function count_ones takes an array of arrays (a nested structure) containing 1s and 0s and counts the total number of 1s. So take a look at this example input: [ [0, 1, 1, 1, 0], [0, 1, 0, 1, 0, 1], [1, 0]]. Our function will return 7 since there are seven 1s.

def count_ones(outer_array):
    count = 0
    for inner_array in outer_array: # Outer Loop: iterates over M inner arrays
        for number in inner_array:  # Inner Loop: iterates over the numbers in the inner array
            if number == 1:
                count += 1
    return count

Big O Efficiency Analysis

While the code uses nested loops, the efficiency is not $O(N^2)$.

1. Define N: Instead of defining $N$ as the size of the outer array, $N$ represents the total number of elements (1s and 0s) contained within all the inner arrays combined.
2. Analyze Steps: The algorithm’s fundamental task is to visit every single number once and perform a comparison.
   • The outer loop moves from one inner array to the next.
   • The inner loop processes the numbers within the current inner array.
   • Together, the nested loops ensure that the counting process only runs for as many numbers as there are in total ($N$).

Since the algorithm simply processes each of the $N$ numbers exactly once, the time complexity is $O(N)$ (linear time).

Palindrome Checker

The function is_palindrome determines if a string reads the same forward and backward.

def is_palindrome(string):
    left_index = 0
    right_index = len(string) - 1
    # Loop runs until left_index reaches the middle of the string:
    while left_index < len(string) // 2:
        if (string[left_index] != string[right_index]):
            return False
        left_index += 1
        right_index -= 1
    return True

Big O Efficiency Analysis

1. Determine N: $N$ is the size (length) of the input string.
2. Analyze Steps: The core logic is within the while loop, which compares characters from the outside-in.
   • The loop condition (left_index < len(string) // 2) ensures the loop only runs until it reaches the midpoint of the string.
   • This means the loop executes approximately $\frac{N}{2}$ times.

According to the rules of Big O notation, constants are ignored. Therefore, the division by 2 is dropped, and the algorithm’s time complexity is $O(N)$ (linear time).

Get All the Products

This algorithm accepts an array of numbers and returns the product of every unique combination of two numbers. To avoid redundant multiplication (e.g., $1\times 2$ and $2\times 1$), the inner loop starts at the index one position to the right of the outer loop’s current index.

def two_number_products(array):
    products = []
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            products.append(array[i] * array[j])
    return products

Big O Efficiency Analysis (Single Array)

1. Determine N: $N$ is the number of items in the input array.
2. Analyze Steps: This involves nested loops, but the inner loop’s length decreases in each iteration.
   • For an array of size $N$, the total number of multiplication steps is calculated by the pattern: $(N-1)+(N-2)+(N-3)+\cdots +1$
   • This sum is a known mathematical series that is equal to approximately $\frac{N^2}{2}$.
   • Since the number of steps is $\frac{N^2}{2}$, and Big O notation ignores constants (the $\frac{1}{2}$), the time complexity of this algorithm is $O(N^2)$ (quadratic time).

Dealing with Multiple Datasets 🔗

This scenario changes the problem: compute the product of every number from a first_array by every number of a second_array.

def two_number_products(array1, array2):
    products = []
    for i in array1:
        for j in array2:
            products.append(i * j)
    return products

Big O Efficiency Analysis (Two Arrays)

1. Determine N and M: Since the two datasets (arrays) are distinct and their sizes can vary independently, combining them into a single $N$ is misleading.
   • Let $N$ be the size of array1.
   • Let $M$ be the size of array2.
2. Analyze Steps: The outer loop runs $N$ times, and the inner loop runs $M$ times for each iteration of the outer loop.
   • Total steps are $N$ multiplied by $M$.

We have no choice but to express the time complexity as: $O(N\times M)$.

This is a new concept: when two distinct datasets must interact multiplicatively (nested loops), we must identify both sizes separately.

Implications of $O(N\times M)$: The efficiency of $O(N\times M)$ exists within a range:

• If $N\approx M$, the complexity is close to $O(N^2)$.
• If $M$ is very small (e.g., $M=1$), the complexity is close to $O(N\times 1)$, or $O(N)$.

Therefore, $O(N\times M)$ can be construed as a range of complexity between $O(N)$ and $O(N^2)$. While this expression is less precise for comparison against algorithms with only one variable, it is the most accurate Big O representation for this type of problem.

Password Cracker

The provided code implements a brute-force password cracker that generates every possible string of a given length using the 26 lowercase English letters.

from string import ascii_lowercase
import itertools
 
def every_password(length):
    for s in itertools.product(ascii_lowercase, repeat=length):
        print("".join(s))

If length is 3, the code will return all possible strings within the range of "aaa" and "zzz". Running this code will print the following:

aaa
aab
aac
aad
aae
...
zzx
zzy
zzz

Time Complexity Analysis

1. Define the Base and Exponent:
   • The base is the number of possibilities for each character (the size of the alphabet, which is 26).
   • The exponent is the length of the password, which we define as $N$ (the input variable length).
2. Calculate Combinations:
   • If the length is 1, there are $26^1=26$ steps.
   • If the length is 2, there are $26\times 26=26^2=676$ steps.
   • If the length is $N$, the total number of unique password combinations is $26^N$.
3. Express in Big O: The number of steps is proportional to $26^N$.

The efficiency of this algorithm is expressed as: $O(26^N)$. This complexity is known as exponential time and is an utterly glacial algorithm. The growth rate is extremely slow:

• Even a “mere” $O(2^N)$ is incredibly slow, eventually becoming slower than cubic time, $O(N^3)$.
• An $O(2^N)$ algorithm doubles in steps every time you add just one element of data.

In the password cracker, each time the length ($N$) increases by one, the number of steps is multiplied by 26. This explosive growth explains why brute-force password cracking is so inefficient.