O Notation Homework and Popcorn hacks

Popcorn Hack #1

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

# Constant time (O(1)) - accessing by index
print("Third item (O(1)):", arr[2])

# Linear time (O(n)) - iterating through the array
print("All items (O(n)):")
for item in arr:
    print(item)

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

Popcorn Hack #2

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

# Example usage
arr = [1, 2, 3]
print_unique_pairs(arr)

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

Time Complexity:

O(n²) (Quadratic Time)

Explanation:

The function uses two nested loops:

• The outer loop runs n times.

• The inner loop runs (n - i - 1) times on each iteration of the outer loop.

• Overall, the number of iterations is roughly n(n - 1)/2, which simplifies to O(n²) in Big-O notation.

Even though we’re only printing each unique pair once, the nested iteration over the array still leads to quadratic time. Let me know if you want this in another language or want to modify it to return the pairs instead of printing!

Popcorn Hack #3

1. Which of these is inefficient for large inputs? ✅ Answer: b) Factorial Time

Explanation: Factorial Time (O(n!)) grows extremely fast as input size increases. Even for relatively small n, the number of operations becomes huge.

The rest grow slower:

a) Linear Time (O(n)) is very efficient.

c) Constant Time (O(1)) is the most efficient.

d) Linearithmic Time (O(n log n)) is still efficient and common in fast sorting algorithms like Merge Sort or Quick Sort.

1. Which of these can be represented by a nested loop? ✅ Answer: c) Quadratic Time

Explanation: Quadratic Time (O(n²)) typically comes from two nested loops each iterating over n elements.

python Copy Edit for i in range(n): for j in range(n): # O(n^2) The other options:

a) Logarithmic Time (O(log n)) often comes from divide-and-conquer (e.g., binary search).

b) Linearithmic Time (O(n log n)) comes from algorithms that mix linear and logarithmic steps, like merge sort.

d) Linear Time (O(n)) is a single loop, not nested.

Homework Hack #1

def perform_operation(arr, complexity):
    if complexity == "constant":
        # O(1) - Access first element
        return arr[0] if arr else None

    elif complexity == "linear":
        # O(n) - Print each element
        for item in arr:
            print(item)

    elif complexity == "quadratic":
        # O(n^2) - Print all pairs
        for i in range(len(arr)):
            for j in range(len(arr)):
                print(f"({arr[i]}, {arr[j]})")

    else:
        print("Unsupported complexity type.")

# Example usage
arr = [5, 10, 15, 20, 25]
print("Constant:")
print(perform_operation(arr, "constant"))

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

print("\nQuadratic:")
perform_operation(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)