Popcorn Hack 1
- Print the third item from the array using constant time (O(1)).
- Print all the items from the array using linear time (O(n)).
arr = [1, 2, 3, 4, 5]
# Constant time O(1)
print("O(1):", arr[2])
# Linear time O(n)
print("O(n):")
for num in arr:
print(num)
O(1): 3
O(n):
1
2
3
4
5
Popcorn Hack 2
arr = [1, 2, 3]
# Unique pairs
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")
print_unique_pairs(arr)
(1, 2)
(1, 3)
(2, 3)
- The time complexity is O(n^2) because it uses a nested loop and each element is paired with naother one.
- Basically, it goes through each element once for the first number, and then again for the paired number
Popcorn Hack 3
Which of these is inefficient for large inputs?
a) Linear Time
b) Factorial Time
c) Constant Time
d) Linearithic Time
This is because it will grow really fast.
Which of these can be represented by a nested loop?
a) Logarithmic Time
b) Linearithmic Time
c) Quadratic Time
d) Linear Time
This is the correct answer because a nested loop goes through each element twice, making it n times n.
Homework Hack
arr = [5, 10, 15, 20, 25]
def time_complexity_demo(arr, complexity_type):
if complexity_type == "constant":
return arr[0]
elif complexity_type == "linear":
for number in arr:
print(number)
elif complexity_type == "quadratic":
for i in arr:
for j in arr:
print(f"({i}, {j})")
print("Constant Time Result:", time_complexity_demo(arr, "constant"))
print("\nLinear Time:")
time_complexity_demo(arr, "linear")
print("\nQuadratic Time:")
time_complexity_demo(arr, "quadratic")
Constant Time Result: 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)