Popcorn Hack 1 – The Even/Odd Check Challenge

Challenge: You need to check if a number is even or odd. Which TWO strategies are the most efficient?

Divide the number by 2 and check if the result is a whole number.
Check if the last digit is 0, 2, 4, 6, or 8 manually
Use the modulus operator (%) to check if the remainder when divided by 2 is 0
Convert the number to a string and check if the last character is an even digit.
Subtract 2 repeatedly until you reach 0 or 1, then check the result.
Generate a list of all even numbers and check if the number is in the list.
Interactive Tip: Write down your answer and explain in two sentences why your choices are the most efficient. (Hint: Methods with O(1) complexity are best for this check.)

ANSWER = 2 and 3 2 –> Only one action step (check if the last element is even) 3 –> only one step (check remainder)

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")

  

Questions + Answers

What is the time complexity of each algorithm? Linear Search: O(n) and Binary Search: O(log n)
How many times faster is binary search than linear search? When data_size = 10,000,000, Binary search is about 100x to 1000x faster than linear search in practice.
What happens if you increase data_size to 20000000? Linear search: Takes about 2x longer. Binary search: Takes only a tiny bit longer (still very fast).

Homework Hack 1

import random
import time

# Bubble Sort Function
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 Function
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 list
original_list = [random.randint(1, 1000) for _ in range(100)]

# Time Bubble Sort
bubble_list = original_list[:]
start_bubble = time.time()
bubble_sort(bubble_list)
end_bubble = time.time()
bubble_time = end_bubble - start_bubble

# Time Merge Sort
merge_list = original_list[:]
start_merge = time.time()
merge_sort(merge_list)
end_merge = time.time()
merge_time = end_merge - start_merge

# Output the results
print(f"Bubble Sort Time: {bubble_time:.6f} seconds")
print(f"Merge Sort Time: {merge_time:.6f} seconds")

if bubble_time < merge_time:
    print("Bubble Sort is faster.")
else:
    print("Merge Sort is faster.")

Final Question Answer

Why does Merge Sort consistently outperform Bubble Sort? Merge Sort uses a split up and try approach with O(n log n) time complexity, while Bubble Sort has a much slower O(n^2) complexity. As the dataset grows, Bubble Sort takes a lot more time due to repeated comparisons and swaps.

Homework Hack 2

import random

# Linear Search Function
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 Function
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

# Create a sorted list of 100,000 numbers
data = list(range(1, 100001))

# Pick a random number from the list
target = random.choice(data)

# Perform searches
linear_comparisons = linear_search(data, target)
binary_comparisons = binary_search(data, target)

# Print results
print(f"Target Number: {target}")
print(f"Linear Search Comparisons: {linear_comparisons}")
print(f"Binary Search Comparisons: {binary_comparisons}")

Final Questions

Which search algorithm is faster, and why? Binary Search is faster because it divides the list in half each time (O(log n)) while Linear Search checks one element at a time (O(n)).
What happens if you run both searches on an unsorted list? Binary Search won’t work correctly because it relies on the list being sorted. Linear Search still works because it just checks each element one by one.