POPCORN HACKS
Hack 1
def method_1_division_check(n):
# Divide and check if result is whole number (not recommended for integers)
return (n / 2).is_integer()
def method_2_last_digit_manual(n):
# Check last digit manually
return str(n)[-1] in {'0', '2', '4', '6', '8'}
def method_3_modulus(n):
# Use modulus
return n % 2 == 0
def method_4_string_last_char(n):
# Convert to string and check last character
return str(n)[-1] in '02468'
def method_5_subtract_until_end(n):
# Subtract 2 repeatedly until 0 or 1
while n > 1:
n -= 2
return n == 0
def method_6_check_list(n):
# Check in list of even numbers (0–100 for demo)
even_numbers = set(range(0, 101, 2))
return n in even_numbers
# Input
number = int(input("Enter a number: "))
# Print results
print("Method 1 - Divide by 2:", "Even" if method_1_division_check(number) else "Odd")
print("Method 2 - Check last digit manually:", "Even" if method_2_last_digit_manual(number) else "Odd")
print("Method 3 - Modulus operator (%):", "Even" if method_3_modulus(number) else "Odd")
print("Method 4 - Convert to string:", "Even" if method_4_string_last_char(number) else "Odd")
print("Method 5 - Subtract until 0 or 1:", "Even" if method_5_subtract_until_end(number) else "Odd")
print("Method 6 - Check against even list:", "Even" if method_6_check_list(number) else "Odd")
Method 1 - Divide by 2: Odd
Method 2 - Check last digit manually: Odd
Method 3 - Modulus operator (%): Odd
Method 4 - Convert to string: Odd
Method 5 - Subtract until 0 or 1: Odd
Method 6 - Check against even list: Odd
Explained: Using the modulus operator (%), and checking the last digit is 0, 2, 4, 6, or 8 manually have O(1) time complexity, meaning they run in constant time regardless of the number’s size. They don’t require loops or extra memory, making them fast and optimal for quickly checking if a number is even or odd. Hence making these 2 strategies the most efficient option
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.402696 seconds
Binary search: 0.000024 seconds
Binary search is approximately 16723x faster
1. complexity of each algorithm
Linear Search – O(n): Linear search goes through each element one by one until it finds the target. If the element is at the end of a dataset, it has to check every element, so the time it takes increases directly with the size of the data.
Binary Search – O(log n): Binary search works only on sorted data and repeatedly cuts the list in half to find the target. This means that even for very large lists, the number of steps it takes grows very slowly compared to the size of the list. (Much more time efficent)
2. How many times faster is binary search than linear search
The line print(f"Binary search is approximately {linear_time/binary_time:.0f}x faster") calculates how many times faster binary search is. in this case its 16723x faster
3. What happens if you increase data_size to 20000000?
- Linear Search: Will take about 2× longer, since it is directly proportional to the list size.
- Binary Search: Will take only slightly longer, because the time grows logarithmically (log base 2 of 20 million is just a bit more than for 10 million).
HOMEWORK HACKS
Hack 1
import time
import random
# 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
# Merge the two halves
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
# Copy remaining elements
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 list
original_list = random.sample(range(1, 1001), 100) # Unique random numbers between 1 and 1000
# Copy list for each algorithm
list_for_bubble = original_list.copy()
list_for_merge = original_list.copy()
# Time Bubble Sort
start = time.time()
bubble_sort(list_for_bubble)
bubble_time = time.time() - start
print(f"Bubble Sort Time: {bubble_time:.6f} seconds")
# Time Merge Sort
start = time.time()
merge_sort(list_for_merge)
merge_time = time.time() - start
print(f"Merge Sort Time: {merge_time:.6f} seconds")
# Compare
if merge_time < bubble_time:
print("Merge Sort is faster.")
else:
print("Bubble Sort is faster.")
Bubble Sort Time: 0.000161 seconds
Merge Sort Time: 0.000082 seconds
Merge Sort is faster.
Question
Why does Merge Sort consistently outperform Bubble Sort?
- Merge Sort has a time complexity of O(n log n), which is much more efficient than Bubble Sort’s O(n^2) for larger lists.
- Merge Sort divides the list and combines them in a sorted manner, reducing the number of comparisons and swaps significantly.
import random
# Linear Search (O(n))
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 (O(log n))
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
data = list(range(1, 100001))
# Pick random target
target = random.choice(data)
print(f"Target: {target}")
# Perform both searches
linear_comparisons = linear_search(data, target)
binary_comparisons = binary_search(data, target)
print(f"Linear Search Comparisons: {linear_comparisons}")
print(f"Binary Search Comparisons: {binary_comparisons}")
Target: 51672
Linear Search Comparisons: 51672
Binary Search Comparisons: 16
Questions:
-
Which search algorithm is faster, and why?
Binary Search is faster because it uses a divide-and-conquer strategy, reducing the search space by half each time (O(log n)), while Linear Search checks every item one by one (O(n)).
-
What happens if you run both searches on an unsorted list?
Binary Search may return incorrect results or fail, because it only works correctly on sorted data. Linear Search still works, as it doesn’t rely on order.