Big O and Algorithmic Efficiency – Notes
Why Efficiency Matters
- Faster applications = better user experience.
- Efficient algorithms conserve memory, CPU, and power.
- Essential for scalability and high-performance systems.
Big O Basics
- O(1) – Constant time (e.g., dictionary access).
- O(log n) – Logarithmic time (e.g., binary search).
- O(n) – Linear time (e.g., loop through list).
- O(n log n) – Linearithmic time (e.g., merge sort).
- O(n²) – Quadratic time (e.g., bubble sort).
Popcorn Hack – Even/Odd Check
Best methods (O(1)):
n % 2 == 0- Bitwise:
n & 1 == 0(not mentioned but also efficient)
String Reversal
s[::-1]: Fast, more memory (new string copy)- Manual insert method: Less memory-efficient, slower
Searching
- Linear Search: O(n), works on unsorted
- Binary Search: O(log n), requires sorted list
Sorting
- Bubble Sort: O(n²), inefficient for large lists
- Merge Sort: O(n log n), efficient, uses extra memory
Trade-Offs
- Faster runtime often requires more memory
- Energy matters for mobile & embedded systems
Real-World Applications
- Database indexing, machine learning, network routing
Diagrams
- Algorithm Efficiency Flow: Input → Time/Space Complexity
- Optimization Trade-off: Faster Time ↔ More Resources
✅ Completed Hacks
Popcorn Hack – Even/Odd Check
Best strategies:
- Use
n % 2 == 0→ Constant time check - Bitwise alternative:
n & 1 == 0→ Also O(1), fast and efficient
Explanation:
- Both avoid loops or conversions.
- Fastest way to determine even/odd since they’re hardware-level operations.
Homework Hack #1: Sorting Showdown
import random, time
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
lst = [random.randint(1, 1000) for _ in range(100)]
a = lst.copy()
start = time.time()
bubble_sort(a)
print("Bubble Sort Time:", time.time() - start)
b = lst.copy()
start = time.time()
merge_sort(b)
print("Merge Sort Time:", time.time() - start)
Bubble Sort Time: 0.0008630752563476562
Merge Sort Time: 0.0005192756652832031
Conclusion:
Merge Sort is consistently faster than Bubble Sort. Bubble Sort does unnecessary comparisons even in nearly sorted arrays.
Homework Hack #2:
def linear_search(arr, target):
count = 0
for i in range(len(arr)):
count += 1
if arr[i] == target:
return count
return -1
def binary_search(arr, target):
left, right = 0, len(arr) - 1
count = 0
while left <= right:
count += 1
mid = (left + right) // 2
if arr[mid] == target:
return count
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = list(range(1, 100001))
target = random.choice(arr)
print("Linear Search Comparisons:", linear_search(arr, target))
print("Binary Search Comparisons:", binary_search(arr, target))
Linear Search Comparisons: 26137
Binary Search Comparisons: 15
Conclusion:
Binary Search is much faster due to halving the search space. Binary Search fails on unsorted lists — sorting is a prerequisite.