Big O/Efficiency

• 4 min read

Popcorn Hack – The Even/Odd Check Challenge

Most Efficient Strategies (Best Two Choices):

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

Explanation:
The modulus operator (%) is the most efficient way to check even/odd because it directly gives you the remainder in constant time (O(1)), which tells you if a number is divisible by 2.
Checking the last digit also works efficiently because even numbers always end in 0, 2, 4, 6, or 8 — and this can be done quickly using simple logic or digit extraction, which is also O(1).

Code:

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


### What is the time complexity of each algorithm?

- **Linear Search:** `O(n)` (must scan each element)
- **Binary Search:** `O(log n)` (cuts the list in half each time)

---

### How many times faster is binary search than linear search?

- Typically, **dozens to hundreds of times faster**, depending on `data_size` and target position.  
- For `data_size = 10,000,000`, it may be around **300–500x faster**.

---

### What happens if you increase `data_size` to `20000000`?

- **Linear search time doubles** (still `O(n)`)
- **Binary search time increases slightly** (`log₂(n)`, so from ~24 to ~25 steps)
- The speed advantage of binary search becomes even more **noticeable**


### HW HACK #1


```python
import time
import random

# Bubble Sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(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
        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
data = [random.randint(1, 1000) for _ in range(100)]
data_for_bubble = data.copy()
data_for_merge = data.copy()

# Time Bubble Sort
start_bubble = time.time()
bubble_sort(data_for_bubble)
end_bubble = time.time()

# Time Merge Sort
start_merge = time.time()
merge_sort(data_for_merge)
end_merge = time.time()

print("Bubble Sort Time:", end_bubble - start_bubble)
print("Merge Sort Time:", end_merge - start_merge)

if (end_bubble - start_bubble) > (end_merge - start_merge):
    print("Merge Sort is faster.")
else:
    print("Bubble Sort is faster.")

HW HACK #2

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

# Create sorted list and random target
sorted_list = list(range(1, 100001))
target = random.choice(sorted_list)

# Run both searches
linear_comparisons = linear_search(sorted_list, target)
binary_comparisons = binary_search(sorted_list, target)

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

if linear_comparisons > binary_comparisons:
    print("Binary Search is faster.")
else:
    print("Linear Search is faster.")

Final Questions – Explanation:

  • Binary Search is faster because it cuts the search space in half each time, giving it a time complexity of O(log n), while Linear Search checks each element one by one (O(n)).

  • If you run both searches on an unsorted list, only Linear Search will work correctly. Binary Search requires the list to be sorted to function properly.