Popcorn Hack 1
# Array of numbers
arr = [1, 2, 3, 4, 5]
# O(1) - Constant time: Accessing the third item
print("O(1) Example:")
print(arr[2]) # Accessing the third item (index 2)
# O(n) - Linear time: Iterating through the entire array
print("\nO(n) Example:")
for num in arr:
print(num)
O(1) Example:
3
O(n) Example:
1
2
3
4
5
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]})")
# Example usage
arr = [1, 2, 3]
print("Unique Pairs:")
print_unique_pairs(arr)
Unique Pairs:
(1, 2)
(1, 3)
(2, 3)
Explanation:
O(n²): The function uses a nested loop where the outer loop runs n times, and the inner loop runs approximately n/2 times on average. This results in a time complexity of ( O(n \times n) = O(n²) ). The inner loop starts at i + 1 to ensure that only unique pairs are printed, avoiding duplicates like (2, 1) when (1, 2) is already printed.
Popcorn Hack 3
- Which of these is inefficient for large inputs?
Answer: b) Factorial Time
- Which of these can be represented by a nested loop?
Answer: c) Quadratic Time
HW Hack
def process_array(arr, complexity):
if complexity == "constant":
# O(1) - Return the first item
return arr[0] if arr else None
elif complexity == "linear":
# O(n) - Print all items in the array
for item in arr:
print(item)
elif complexity == "quadratic":
# O(n²) - Print all pairs of items in the array
for i in range(len(arr)):
for j in range(len(arr)):
print(f"({arr[i]}, {arr[j]})")
else:
return "Invalid complexity specified."
# Example usage
arr = [5, 10, 15, 20, 25]
# Test constant time
print("Constant Time:", process_array(arr, "constant"))
# Test linear time
print("\nLinear Time:")
process_array(arr, "linear")
# Test quadratic time
print("\nQuadratic Time:")
process_array(arr, "quadratic")
Constant Time: 5
Linear Time:
5
10
15
20
25
Quadratic Time:
(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)