Big o hw

Big O HW

Popcorn #1

arr = [1, 2, 3, 4, 5]

print("Third item (O(1)):", arr[2])

print("All items (O(n)):")
for item in arr:
    print(item)

Output

Third item (O(1)): 3
All items (O(n)):
1
2
3
4
5

Popcorn #2

# Popcorn Hack #2
arr = [1, 2, 3]

def print_unique_pairs(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            print(f"({arr[i]}, {arr[j]})")

print_unique_pairs(arr)

Output

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

This is quadratic time because for each element in the array, the function loops through the remaining elements to form a pair. As the array grows, the number of pairings grows roughly as the square of the number of elements.

Popcorn #3

Which of these is inefficient for large inputs?

a) Linear Time b) Factorial Time c) Constant Time d) Linearithic Time

Correct Answer: b) Factorial Time

Which of these can be represented by a nested loop?

a) Logarithmic Time b) Linearithmic Time c) Quadratic Time d) Linear Time

Correct Answer: c) Quadratic Time

HW HACK

def perform_operation(arr, complexity):
    if complexity == "constant":
        return arr[0]
    
    elif complexity == "linear":
        for item in arr:
            print(item)
    
    elif complexity == "quadratic":
        for i in range(len(arr)):
            for j in range(len(arr)):
                print(f"({arr[i]}, {arr[j]})")
    
    else:
        print("Unsupported time complexity.")

arr = [5, 10, 15, 20, 25]
perform_operation(arr, "constant")    
perform_operation(arr, "linear")     
perform_operation(arr, "quadratic")