If my function has two nested for loops does it run in quadratic time?

Your logic to analyze and calculate the complexity of the algorithms is correct. However, I suspect your teacher might not be please with the code you wrote.

Issue with your linear function

def find_min_linear(a_list):
    return min(a_list)

You are asked to write a function that returns the minimum of a list, and to do that, you... used the python builtin function that returns the minimum of a list.

This would be a great idea for any practical application, as the python builtin function is likely to be faster than any function your wrote yourself; and you can trust that it doesn't have bugs, rather than waste time checking your own code for bugs.

But your teacher might be more interested in you coming up with an algorithm to find the minimum, than in you knowing that there already is a python builtin function that does that. The min function is indeed linear, but this function only exists because someone was able to come up with a linear algorithm in the first place, and used it to implement the function . In fact, I find it quite unsettling that your teacher didn't explicitly forbid you from using the python builtins min and max for this assignment. If I were a student, I would probably mention that the builtin exists and executes in linear time, then I would write my own function without using the existing one.

Issue with your quadratic function

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
        for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

Technically, your function works, and it is quadratic. However, the inner for loop is troubling. The variable item is never used; its only purpose is making sure the loop has a n iterations (where n is the length of the list). The body of the loop will always execute exactly the same; the condition in the if will either always be true, or always be false; and if it is true, then min_number = a_number will just write the same value to the same variable, over and over again.

In other words: executing this if statement repeatedly in a for loop makes no sense; just execute it once.

def find_min_quadratic(a_list):
    min_number = aList[0]
    for a_number in a_list:
    #    for item in range(len(a_list)):
            if min_number > a_number:
                min_number = a_number
    return min_number

Tadaaaaa! With just one line fewer the algorithm still executes correctly and return the minimum of the list.

The algorithm is linear now, not quadratic. Your teacher asked you for a quadratic algorithm. You might think it's okay to add a for loop to make your algorithm quadratic. That's technically true, but then the following algorithm would also work:

def find_min_quadratic(a_list):
    min_number = find_min_linear(a_list)
    for item in range(len(a_list)**2):
        beebboop = 57
    return min_number

There is no arguing this function is quadratic - we explicitly included a loop that runs for n^2 iterations. But your teacher might have a feeling you're making fun of them.

Besides, if you read carefully, the text of your assignment says "The first function should compare each number to every other number on the list.". Your quadratic function didn't do that.

A quadratic algorithm

You already found a linear algorithm (by removing one line from your quadratic function) so now you still have to find a quadratic function. This is a bit counterintuitive and personally, I strongly dislike this assignment. Writing algorithms usually follow these steps:

1. express a problem
2. find an algorithm to solve the problem
3. analyze the complexity of your algorithm
4. find a new algorithm to solve the problem with a lower complexity

So an assignment along those lines would make a lot of sense:

1. Write a function to find the minimum of a list
2. Analyse the complexity of your function
3. If your function is not linear, then write a new function to find the minimum of a list in linear time.

If you've already found the linear function, then looking for a less efficient function is awkward, and this resulted in you adding a for loop that just wastes time for no reason.

I think the point of the assignment is not to artificially make a less efficient function, but try to come up with a completely different algorithm, and then understand that not all algorithms are equally efficient.

Your teacher explicitly said "The first function should compare each number to every other number on the list.". So we can use that to write a new function:

def find_min_quadratic(a_list):
    # ...
    for a in a_list:
        # ...
        for b in a_list:
            if a > b:
                # ...
        # ...

Try to fill in the blanks so that this returns the minimum. You can add other variables, you can add other if statements, but do not add other for loops. Hint: how to decide whether an element a is the minimum? Can we find whether a is the minimum thanks to the for b in a_list loop?

Your logic is correct, the way you analyze the method you implemented yourself is exactly how it should be done.

What could be confusing is the 2nd one, in that case you are calling some function, which is already implemented in the language library itself. And that also have own complexity, in this case O(n).

If you want to make your own method with linear complexity then you can implement it this way:

1. define min variable
2. loop through the array and compare the value in loop with the defined min value
3. if min > looped value then reassign it to min

The quadratic solution is as follows:

def findMinQuad(aList):
    overallmin = alist[0]
    for i in aList:
        issmallest = True 
        for j in a List: 
            if i > j:
                issmallest = False
        if issmallest: 
                overallmin = i 

    return overallmin

Since we are iterating over our input aList twice witht the nested for loops, we know the answer is quadratic time O(n^2). And the nested loops also make sure that we compare each number to every other number in the list.

The linear solution is the following:

def findMinLin(aList):
    minsofar = aList[0]
    for i in aList:
        if i < minsofar:
            minsofar = i
    return minsofar

This one is pretty self explanatory, we just assume that the first number is the minimum, and then we iterate over the list to see if we find a smaller number. If we do, then that number is the new smallest number, by the end of the loop whatever is saved as the smallest number will, in fact, be the smallest number.