Popcorn Hack 1
You need to check if a number is even or odd. Which TWO strategies are the most efficient?
-
Check if the last digit is 0, 2, 4, 6, or 8 manually
This is efficient because there are only 5 checks, which are pretty easy. -
Use the modulus operator (%) to check if the remainder when divided by 2 is 0
This is efficient because it is quick for a program to check and doesn’t depend on input size.
Popcorn Hack 2
What is the time complexity of each algorithm?
- Linear Search:
O(n) - Binary Search:
O(log n)
How many times faster is binary search than linear search?
log₂(10,000,000) = 23- Binary search can be up to ~434,783 times faster than linear search in theory.
What happens if you increase data_size to 20,000,000?
- Linear Search: Time roughly doubles
- Binary Search: Time increases slightly, but much less than linear search
Homework hack 1:
``` import random
import time
# Generate a list of 100 random integers between 1 and 1000
original_list = [random.randint(1, 1000) for _ in range(100)]
# Bubble Sort
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]
# Merge Sort
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
# Make copies so each sort gets the same input
bubble_list = original_list.copy()
merge_list = original_list.copy()
# Time Bubble Sort
start_time = time.time()
bubble_sort(bubble_list)
bubble_duration = time.time() - start_time
# Time Merge Sort
start_time = time.time()
merge_sort(merge_list)
merge_duration = time.time() - start_time
# Output Results
print(f"Bubble Sort Time: {bubble_duration:.6f} seconds")
print(f"Merge Sort Time: {merge_duration:.6f} seconds")
# Determine which is faster
if bubble_duration < merge_duration:
print("Bubble Sort is faster.")
else:
print("Merge Sort is faster.")
```
Output
``` Bubble Sort Time: 0.003212 seconds Merge Sort Time: 0.000312 seconds Merge Sort is faster. Final question/ reflection Why does Merge Sort consistently outperform Bubble Sort? Merge Sort has a time complexity of O(n log n), while Bubble Sort is O(n²). This means Merge Sort scales much better as input size increases, making it significantly faster for large or even moderately sized datasets. ```
Homework hack 2
```import random
# Generate a sorted list from 1 to 100,000
data = list(range(1, 100001))
# Pick a random target from the list
target = random.choice(data)
# Linear Search with comparison count
def linear_search(arr, target):
count = 0
for i in range(len(arr)):
count += 1
if arr[i] == target:
return count
return -1
# Binary Search with comparison count
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
# Run both searches
linear_comparisons = linear_search(data, target)
binary_comparisons = binary_search(data, target)
# Output results
print(f"Target: {target}")
print(f"Linear Search Comparisons: {linear_comparisons}")
print(f"Binary Search Comparisons: {binary_comparisons}")
```
Output:
```Target: 74528 Linear Search Comparisons: 74528 Binary Search Comparisons: 17 Which search algorithm is faster, and why? Binary Search is faster because it uses a divide-and-conquer strategy with O(log n) complexity, while Linear Search checks each element one-by-one with O(n) complexity. What happens if you run both searches on an unsorted list? Linear Search still works because it doesn’t rely on order. Binary Search will give incorrect results or fail because it requires the list to be sorted. ```