Big O Notation

Popcorn Hack 1

arr = [1, 2, 3, 4]
# constant time complexity
print(arr[2])

# logarithmic time complexity
for i in arr:
    print(i)

3
1
2
3
4

Popcorn Hack 2

arr = [1, 2, 3]
for i in range(len(arr)): 
    for j in range(i+1, len(arr)):
        print(f"({arr[i]}, {arr[j]})")
        
# Time complexity: this is O(n^2) because for each element in the array, we are iterating through the rest of the elements. Nested loops require a quadratic time complexity because each element is compared with each element that comes after it. 

(1, 2)
(1, 3)
(2, 3)

Popcorn Hack 3

Inefficient for large inputs: B, factorial time. It grows very quickly.
Represented by a nested loop: C, quadratic time

Homework Hack

def operate(arr, complexity):
    if complexity == "constant":
        return arr[0]
    
    if complexity == "linear":
        for item in arr:
            print(item)
    
    if complexity == "quadratic":
        for i in arr:
            for j in arr:
                print((i, j))

arr = [5, 10, 15, 20, 25]

print("Constant:")
print(operate(arr, "constant"))

print("\nLinear:")
operate(arr, "linear")

print("\nQuadratic:")
operate(arr, "quadratic")

Constant:
5

Linear:
5
10
15
20
25

Quadratic:
(5, 5)
(5, 10)
(5, 15)
(5, 20)
(5, 25)
(10, 5)
(10, 10)
(10, 15)
(10, 20)
(10, 25)
(15, 5)
(15, 10)
(15, 15)
(15, 20)
(15, 25)
(20, 5)
(20, 10)
(20, 15)
(20, 20)
(20, 25)
(25, 5)
(25, 10)
(25, 15)
(25, 20)
(25, 25)