Popcorn Hack 1
Most Efficient Strategies:
Use the modulus operator (% 2 == 0)
Check if the last digit is 0, 2, 4, 6, or 8
Why: Both are O(1) operations that require minimal processing and no iteration or extra memory. They provide instant results with simple logic.
Popcorn Hack 2
import time
import random
# Generate a large sorted list
data_size = 20000000
sorted_data = sorted(random.sample(range(20000000), data_size))
# Target to find (worst case for linear search)
target = sorted_data[-1] # Last element
# O(n) - Linear Search
def linear_search(arr, target):
for i, element in enumerate(arr):
if element == target:
return i
return -1
# O(log n) - Binary Search
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Compare performance
print("Testing with data size:", data_size)
start = time.time()
linear_result = linear_search(sorted_data, target)
linear_time = time.time() - start
print(f"Linear search: {linear_time:.6f} seconds")
start = time.time()
binary_result = binary_search(sorted_data, target)
binary_time = time.time() - start
print(f"Binary search: {binary_time:.6f} seconds")
print(f"Binary search is approximately {linear_time/binary_time:.0f}x faster")
Testing with data size: 20000000
Linear search: 0.589462 seconds
Binary search: 0.000048 seconds
Binary search is approximately 12362x faster
What is the time complexity of each algorithm?
Linear:O(n)
Binary: O(log n)
How many times faster is binary search than linear search?
10500 times
What happens if you increase data_size to 20000000?
Linear search gets slower and slower
Homework Hack 1
import random
import 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
# Generate random data
data = [random.randint(1, 1000) for _ in range(100)]
# Measure Bubble Sort time
arr1 = data[:]
start = time.time()
bubble_sort(arr1)
end = time.time()
bubble_time=end-start
print(f"Bubble Sort Time: {end - start:.6f} seconds")
# Measure Merge Sort time
arr2 = data[:]
start = time.time()
merge_sort(arr2)
end = time.time()
merge_time=end-start
print(f"Merge Sort Time: {end - start:.6f} seconds")
# Compare times
if bubble_time < merge_time:
print("Bubble Sort is faster")
elif bubble_time > merge_time:
print("Merge Sort is faster")
else:
print("Both algorithms took the same time")
Bubble Sort Time: 0.000226 seconds
Merge Sort Time: 0.000105 seconds
Merge Sort is faster
Merge Sort uses a divide-and-conquer strategy that reduces the number of comparisons needed for sorting. It operates in O(n log n) time, making it significantly faster than Bubble Sort’s O(n²) time, especially on larger datasets.
Homework Hack #2: Search Race – Code Edition
import random
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
# Generate sorted list and pick a random target
arr = list(range(1, 100001))
target = random.choice(arr)
# Execute searches
print(f"Target: {target}")
print(f"Linear Search Comparisons: {linear_search(arr, target)}")
print(f"Binary Search Comparisons: {binary_search(arr, target)}")
Target: 5128
Linear Search Comparisons: 5128
Binary Search Comparisons: 15
Which search algorithm is faster, and why?
Binary Search is faster because it reduces the search range by half with each comparison, resulting in O(log n) time. Linear Search must examine each element individually, leading to O(n) time.
What happens if the list is unsorted?
Binary Search will fail or produce incorrect results since it requires sorted data. Linear Search will still function correctly, albeit inefficiently.