Common Big O Complexities Notation Complexity Class Description O(1) Constant Time Execution time is the same regardless of input size. O(log n) Logarithmic Time Execution time increases logarithmically with input size. O(n) Linear Time Execution time grows proportionally to input size. O(n log n) Linearithmic Time Common in efficient sorting algorithms like Merge Sort and Quick Sort. O(n²) Quadratic Time Execution time grows quadratically with input size. O(2ⁿ) Exponential Time Execution time doubles with each additional element. O(n!) Factorial Time Execution time grows factorially, very inefficient for large inputs.
Popcorn hack #1
arr = [1, 2, 3, 4, 5]
# Print the third item (index 2) - O(1)
print("Third item (O(1)):", arr[2])
# Print all items - O(n)
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):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
print(f"({arr[i]}, {arr[j]})")
# Test
arr = [1, 2, 3]
print_unique_pairs(arr)
(1, 2)
(1, 3)
(2, 3)
Even though the inner loop starts from i + 1 to avoid duplicates, it’s a nested loop, and in the worst case, the number of pairings grows with the square of the number of items. So the time complexity is quadratic (O(n²)).
Popcorn hack #3
Which of these is inefficient for large inputs? b— Factorial Time Explanation: Factorial time (O(n!)) grows extremely fast as input increases, making it very inefficient for large datasets.
Which of these can be represented by a nested loop? c— Quadratic Time Explanation: Nested loops over the same input (like double for loops) usually result in O(n²), which is quadratic time.
Homework hack
def time_complexity_demo(arr, complexity):
if complexity == "constant":
# O(1) - Return the first element
return arr[0]
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 arr:
for j in arr:
print(f"({i}, {j})")
else:
print("Unsupported complexity type.")
# Example usage:
arr = [5, 10, 15, 20, 25]
print("Constant time result:", time_complexity_demo(arr, "constant"))
print("\nLinear time result:")
time_complexity_demo(arr, "linear")
print("\nQuadratic time result:")
time_complexity_demo(arr, "quadratic")
Constant time result: 5
Linear time result:
5
10
15
20
25
Quadratic time result:
(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)