"""minlist.py

 from
 runestone.academy/runestone/books/published/
 pythonds/AlgorithmAnalysis/BigONotation.html

 Write two Python functions to find the minimum number in a list. The
 first function should compare each number to every other number on
 the list. 𝑂(𝑛2). The second function should be linear 𝑂(𝑛).

   $ python minlist.py
    actual min is 3
    minsingle gives 3
    minpairs gives 3

 TODO:
    * Count and return number of steps in each function.
    * Generate lists of size N of random integers.
    * Loop over values of N, check O() behavior.

 Jim Mahoney | Feb 22 2021 | cs.bennington.college
"""

def minpairs(values):
    """ Look at all pairs. As soon as we find one that's smaller than
        all the others, return it. """
    # Loop within a loop; O(n**2)
    for a in values:
        a_is_smallest = True
        i = 0
        while a_is_smallest and i < len(values):
            a_is_smallest = a <= values[i]
            i += 1
        if a_is_smallest:
            return a

def minsingle(values):
    """ Look at each value. Remember smallest seen so far """
    # Once through loop; O(n)
    smallest = float('inf')
    for a in values:
        if a < smallest:
            smallest = a
    return smallest

def main():
    numbers = [20, 10, 5, 6, 3, 30, 11]
    print(f" actual min is {min(numbers)}")
    print(f" minsingle gives {minsingle(numbers)}")
    print(f" minpairs gives {minpairs(numbers)}")

main()