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?

  1. Divide the number by 2 and check if the result is a whole number.
  2. Check if the last digit is 0, 2, 4, 6, or 8 manually
  3. Use the modulus operator (%) to check if the remainder when divided by 2 is 0
  4. Convert the number to a string and check if the last character is an even digit.
  5. Subtract 2 repeatedly until you reach 0 or 1, then check the result.
  6. 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.)

Most Efficient Strategies:

  1. Check if the last digit is 0, 2, 4, 6, or 8 manually
  2. Use the modulus operator (%) to check if the remainder when divided by 2 is 0

Why These Are Efficient: The modulus operator is a constant-time (O(1)) arithmetic operation that directly checks if a number is divisible by 2, making it fast and simple. Checking the last digit is also O(1) and leverages the fact that even numbers end in even digits, which is especially efficient for integers represented as strings or when parsing user input.

import time
import random

# Generate a large sorted list
data_size = 20000000
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: 20000000
Linear search: 9.324526 seconds
Binary search: 0.000092 seconds
Binary search is approximately 101584x faster

Popcorn Hack #2

Time Complexity

  • Linear Search: O(n)
    It checks each element one by one until it finds the target (or reaches the end).
  • Binary Search: O(log n)
    It repeatedly divides the search range in half, making it exponentially faster.

How Many Times Faster? Let’s say you run the code with data_size = 10,000,000 (10 million):

  • Linear Search Time: 4.285923 seconds.
  • Binary Search Time: 0.000109 seconds.
    Binary search is approximately 39164x faster

What Happens if data_size = 20,000,000?

  • Linear Search: 9.324526 seconds. Takes twice as long, because time increases linearly.
  • Binary Search: 0.000092 seconds. Increases by just one extra step (log₂ of the size goes from ~23.2 to ~24.2), so the time increase is negligible.
    Binary search is approximately 101584x faster.

TL;DR Binary search scales much better because of its logarithmic time. If you double the dataset size:

  • Linear search doubles in time.
  • Binary search barely changes.

College Board Notes:

What’s efficient?
other methods: 2^n, n factorial
college board says all listed are efficient. Programs say O(n log n)
n^2 : nested for loops are inefficent.

Homework Hack

import random

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

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

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

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