Popcorn Hack 1
arr = [1, 2, 3, 4, 5]
# Constant time (O(1)) - Access by index
print(arr[2]) # Third item (index starts at 0)
# Linear time (O(n)) - Loop through all items
for item in arr:
print(item)
Explanation:
arr[2] is constant time because it’s a direct index access.
The for loop is linear time because it processes each element once.
Accessing an array element by index is O(1) because it jumps directly to that position without checking others. Looping through the array is O(n) because it visits each item one by one, taking more time as the array gets bigger.
Popcorn Hack #2
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]})")
arr = [1, 2, 3]
print_unique_pairs(arr)
Explanation: This uses two nested loops where each element is paired with every following element. As the array size grows, the number of comparisons grows roughly with the square of the size, making it quadratic time.
Popcorn Hack #3
- Which is inefficient for large inputs? Answer: b) Factorial Time
Explanation: Factorial time (O(n!)) grows extremely fast and becomes unusable even for small inputs. It’s much slower than linear (O(n)), constant (O(1)), or linearithmic (O(n log n)) time.
- Which can be represented by a nested loop? Answer: c) Quadratic Time
Explanation: Quadratic time (O(n²)) often results from a nested loop, where each element is compared with every other element.
a) Logarithmic Time is usually from divide-and-conquer (e.g. binary search).
b) Linearithmic Time is from divide-and-conquer with a merge step (e.g. merge sort).
d) Linear Time comes from a single loop over all elements.
Homework Hack #1
def perform_operation(arr, complexity):
if complexity == "constant":
return arr[0] # O(1)
elif complexity == "linear":
for item in arr: # O(n)
print(item)
elif complexity == "quadratic":
for i in range(len(arr)): # O(n^2)
for j in range(len(arr)):
print(f"({arr[i]}, {arr[j]})")
else:
print("Unsupported complexity")
# Example usage:
arr = [5, 10, 15, 20, 25]
perform_operation(arr, "quadratic")
The function uses if statements to check the given time complexity and performs matching operations: constant time returns the first item, linear time prints each item once, and quadratic time prints all possible pairs using nested loops.