Popcorn Hack 1
The two most efficient strategies are:
- Use the modulus operator (%) to check if the remainder when divided by 2 is 0.
- Check if the last digit is 0, 2, 4, 6, or 8 manually.
This is because both methods are O(1) (constant time) operations. They require just one simple check without loops or complex calculations. Modulus is the classic mathematical way, while checking the last digit is a quick shortcut when numbers are already available as digits or strings.
Popcorn Hack 2
import time
import random
# Generate a large sorted list
data_size = 10000000
sorted_data = sorted(random.sample(range(100000000), 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: 10000000
Linear search: 0.881943 seconds
Binary search: 0.000031 seconds
Binary search is approximately 28455x faster
When the data size is increased to 20000000, the time for linear search increases by around 0.2 seconds and the time for binary search remains practically the same, showing binary search may be better for larger data sets.
These are the results:
Testing with data size: 20000000
Linear search: 1.044598 seconds
Binary search: 0.000039 seconds
Binary search is approximately 26716x faster
Homework Hack 1
import random
import time
# 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
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
# Merging the sorted halves
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Check if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Generate a list of 100 random numbers between 1 and 1000
original_list = [random.randint(1, 1000) for _ in range(100)]
# Test Bubble Sort
list_for_bubble = original_list.copy()
start_bubble = time.time()
bubble_sort(list_for_bubble)
end_bubble = time.time()
# Test Merge Sort
list_for_merge = original_list.copy()
start_merge = time.time()
merge_sort(list_for_merge)
end_merge = time.time()
# Output times
time_bubble = end_bubble - start_bubble
time_merge = end_merge - start_merge
print(f"Bubble Sort Time: {time_bubble:.6f} seconds")
print(f"Merge Sort Time: {time_merge:.6f} seconds")
# Which is faster
if time_bubble < time_merge:
print("Bubble Sort is faster.")
else:
print("Merge Sort is faster.")
Bubble Sort Time: 0.000228 seconds
Merge Sort Time: 0.000093 seconds
Merge Sort is faster.
Why does merge sort always outperform bubble sort?
Merge Sort consistently outperforms Bubble Sort because it uses a divide-and-conquer strategy, breaking the list into smaller parts and sorting them efficiently, achieving O(n log n) time complexity. In contrast, Bubble Sort must compare every pair repeatedly, leading to a much slower O(n²) time, especially as the list grows.
Homework Hack 2
import random
# Linear Search
def linear_search(arr, target):
comparisons = 0
for i in range(len(arr)):
comparisons += 1
if arr[i] == target:
return i, comparisons
return -1, comparisons
# Binary Search
def binary_search(arr, target):
comparisons = 0
left, right = 0, len(arr) - 1
while left <= right:
comparisons += 1
mid = (left + right) // 2
if arr[mid] == target:
return mid, comparisons
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1, comparisons
# Generate a sorted list of 100,000 numbers
sorted_list = list(range(1, 100001))
# Pick a random number to search for
target_number = random.choice(sorted_list)
# Search using Linear Search
index_linear, comparisons_linear = linear_search(sorted_list, target_number)
# Search using Binary Search
index_binary, comparisons_binary = binary_search(sorted_list, target_number)
# Output the results
print(f"Target Number: {target_number}")
print(f"Linear Search Comparisons: {comparisons_linear}")
print(f"Binary Search Comparisons: {comparisons_binary}")
# Which search algorithm is faster?
if comparisons_linear < comparisons_binary:
print("Linear Search is faster (unexpected!)")
else:
print("Binary Search is faster (as expected!)")
Target Number: 63001
Linear Search Comparisons: 63001
Binary Search Comparisons: 17
Binary Search is faster (as expected!)
Which search algorithm is faster, and why?
Binary Search is faster because it divides the search space in half every time (O(log n) time complexity), while Linear Search checks every element one-by-one (O(n) time complexity).
What happens if you run both searches on an unsorted list?
Linear Search still works because it doesn’t rely on order, it just checks each item. Binary Search will fail or give wrong results because it assumes the list is already sorted to divide it correctly.