Algorithm Efficiency Hacks

Popcorn Hack – Even/Odd Check Challenge

Prompt: Pick the TWO most efficient strategies

  • Divide the number by 2 and check if the result is a whole number – Not ideal (Floating point operations = slightly less efficient).
  • Check if the last digit is 0, 2, 4, 6, or 8 manually – O(1)
  • Use the modulus operator % 2 == 0 – O(1)
  • Convert to string and check last character – O(n) in the worst case.
  • Subtract 2 repeatedly – O(n) (very slow for large numbers).
  • Generate a list of all even numbers – O(n) and memory wasteful.

Answer:

  • Use the modulus operator
  • Check the last digit manually

Explanation:
Both the modulus operator and digit-check method are constant time operations (O(1)), making them highly efficient. They avoid unnecessary iteration or conversion, optimizing performance and memory.

String Reversal Challenge

Which method is better for performance-critical apps?

  • Speed-Optimized (s[::-1]) is faster (O(n)) but uses more memory.
  • Memory-Optimized is slower due to insert(0, c) being O(n) per character, leading to O(n²).

Answer:
Use the speed-optimized slicing method (s[::-1]) in performance-critical apps. It has linear time complexity and is highly optimized in Python’s internal C implementation, even if it uses more memory.

Popcorn Hack:

import time
import random

def linear_search(arr, target):
    comparisons = 0
    for i in range(len(arr)):
        comparisons += 1
        if arr[i] == target:
            return comparisons
    return comparisons

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    while left <= right:
        comparisons += 1
        mid = (left + right) // 2
        if arr[mid] == target:
            return comparisons
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return comparisons

arr = list(range(1, 10000001))
target = random.choice(arr)

start = time.time()
linear = linear_search(arr, target)
print("Linear comparisons:", linear, "Time:", time.time() - start)

start = time.time()
binary = binary_search(arr, target)
print("Binary comparisons:", binary, "Time:", time.time() - start)


Linear comparisons: 1394583 Time: 0.2737619876861572
Binary comparisons: 24 Time: 0.00018072128295898438

Homework Hack 1:

import random, time

# Generate random list
arr = [random.randint(1, 1000) for _ in range(100)]

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

# Time them
arr1 = arr[:]
arr2 = arr[:]

start = time.time()
bubble_sort(arr1)
bubble_time = time.time() - start

start = time.time()
merge_sort(arr2)
merge_time = time.time() - start

print(f"Bubble Sort Time: {bubble_time:.5f} sec")
print(f"Merge Sort Time: {merge_time:.5f} sec")


Bubble Sort Time: 0.00325 sec
Merge Sort Time: 0.00125 sec

Final Answer: Merge Sort consistently outperforms Bubble Sort because it minimizes comparisons through its divide-and-conquer approach. Bubble Sort performs many unnecessary comparisons and swaps, especially on large datasets.

Homework Hack 2:

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

arr = list(range(1, 100001))
target = random.choice(arr)

linear_comparisons = linear_search(arr, target)
binary_comparisons = binary_search(arr, target)

print(f"Linear Search Comparisons: {linear_comparisons}")
print(f"Binary Search Comparisons: {binary_comparisons}")


Linear Search Comparisons: 7474
Binary Search Comparisons: 17

Final Answers:

  • Binary Search is faster because it cuts the search space in half each time, giving it O(log n) performance.

  • If run on an unsorted list, Binary Search may fail or return incorrect results—it requires sorted input.