Comparing O(n) and O(n^2)

Author: Jackie Lu

Date: 2021, Aug. 26

Table of Contents

• Note
• O(n) function
• O(n^2) function
• References

Note

The Python code for the functions, unit tests, comparisons, as well as the data in csv format and image can be found in this link to the code.

O(n) function

# find_min_n.py
import math


def find_min_n(numberList):
    """
    Find the minimum number in a list of numbers
    
    Keyword arguments:
    numberList -- the list of numbers
    
    Returns:
    min -- the minimum number from numberList
    """
    min = math.inf
    for number in numberList:
        if number < min:
            min = number
    return min

This function is O(n) because it loops through all of the elements in the array once.

O(n^2) function

# find_min_n2.py
import math


def find_min_n2(numberList):
    """
    Find the minimum number in a list of numbers.
    
    Keyword arguments:
    numberList -- the list of numbers
    
    Returns:
    min -- the minimum number from numberList
    """
    min = math.inf
    # Loop through every number
    for number1 in numberList:
        is_min = True
        # Compare number1 with every other number in numberList
        for number2 in numberList:
            # If number1 is larger than any other number, then it's not min
            if number1 > number2:
                is_min = False
        # If the minimum number is found, return
        if is_min == True:
            min = number1
            return min
    return min

This function is O(n^2) because of the nested loop.

Here's a plot of the execution time:

References

Links to the resources I used can be found here:
https://runestone.academy/runestone/books/published/pythonds/AlgorithmAnalysis/BigONotation.html