Popcorn Hack 1
Here’s an array of numbers:
arr = [1, 2, 3, 4, 5]
arr[2] is a direct access to an element in a list by its index — this takes constant time, O(1). The for loop goes through each item one by one, so it takes linear time, O(n), where n is the number of items in the list.
arr = [1, 2, 3, 4, 5]
# Constant time (O(1)) access to the third item (index 2)
print("Third item (O(1)):", arr[2])
# Linear time (O(n)) to print all items
print("All items (O(n)):")
for item in arr:
print(item)
Popcorn Hack 2
Given the array of numbers from 1-3 (arr = [1,2,3]). Write a function that prints all the different unique pairs of numbers from the array. For example the output of this array should be: (1,2) (1,3) (2,3)
Addtionally, what time complexity is this code? Write a small explanation. There are two nested loops. For an array of length n, the outer loop runs n times. The inner loop runs fewer times each iteration, but overall the number of iterations is roughly n(n-1)/2, which is O(n²).
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(arr)
(1,2)
(1,3)
(2,3)
Popcorn Hack #3
Which of these is inefficient for large inputs?
a) Linear Time
b) Factorial Time
c) Constant Time d) Linearithic Time
Which of these can be represented by a nested loop?
a) Logarithmic Time b) Linearithmic Time
c) Quadratic Time
d) Linear Time
Homework Hack
Write a function that takes the following inputs:
An array: arr = [5, 10, 15, 20, 25] A string representing the time complexity: “constant”, “linear”, “quadratic”, etc. The function should perform operations on the array based on the given time complexity. For example:
If the string is “constant”, return the first item of the array. If the string is “linear”, print all the items in the array. If the string is “quadratic”, print all pairs of items in the array.
def run_by_time_complexity(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
for item in arr:
print(item)
elif complexity == "quadratic":
# O(n^2): Print all unique 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 Time:")
print(run_by_time_complexity(arr, "constant"))
print("\nLinear Time:")
run_by_time_complexity(arr, "linear")
print("\nQuadratic Time:")
run_by_time_complexity(arr, "quadratic")