Big O and Algorithm Efficiency Hacks

• 6 min read

Tri 3 Team Teach Hacks

Popcorn Hack 1

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

Why these are the most efficient:
Both methods are O(1) operations, meaning they run in constant time regardless of the size of the input. The modulus operator directly determines evenness, while checking the last digit is a quick shortcut for base-10 integers.

Challenge:

Run the code above and experiment with different string lengths.
Which method would you choose for a performance-critical application and why?

Answer:

✅ Choose the speed_optimized_method(s[::-1]) for a performance-critical application.

Why?

  • The slicing method is implemented in C under the hood and operates in linear time O(n) with minimal overhead.
  • It consistently outperforms the manual insert method in both speed and memory efficiency, especially as the string length increases.
  • The memory_optimized_method incurs high memory costs due to repeated insertions at the beginning of the list, making it significantly slower and more memory-intensive for large inputs.

Popcorn Hack 2

Search Algorithm Analysis

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

Time Complexity:

  • Linear Search: O(n) — Scans each item until it finds the target.
  • Binary Search: O(log n) — Cuts the search range in half every step.
  • In a typical run: 
    Linear search: ~2.3 seconds
Binary search: ~0.00005 seconds
Binary search is approximately ~46000x faster
  • The exact number may vary by system, but binary search is orders of magnitude faster.

What Happens if You Increase data_size to 20000000?

  • Linear Search: Time roughly doubles (O(n)).
  • Binary Search: Time increases minimally (O(log n)).
  • ➕ Binary search becomes even more dominant in larger datasets.

✅ Conclusion:

Use binary search for large sorted datasets — it is vastly more efficient than linear search.

Homework Hack 1

import time
import random

# Generate a list of 100 random numbers between 1 and 1000
data = [random.randint(1, 1000) for _ in range(100)]
data_for_bubble = data.copy()
data_for_merge = data.copy()

# 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:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

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

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

# Output 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.")
elif merge_time < bubble_time:
    print("Merge Sort is faster.")
else:
    print("Both sorting algorithms took the same time.")


Bubble Sort Time: 0.014363 seconds
Merge Sort Time:  0.002733 seconds
Merge Sort is faster.

Merge Sort consistently outperforms Bubble Sort because it has a time complexity of O(n log n), which scales much more efficiently for large datasets. In contrast, Bubble Sort has a time complexity of O(n²), making it much slower as the size of the list grows. Merge Sort divides the list into smaller sublists and sorts them recursively, while Bubble Sort repeatedly compares and swaps adjacent elements, which results in more unnecessary comparisons and swaps.

Homework Hack 2

import random

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

# Pick a random number in the list
target = random.choice(sorted_list)

# Linear Search
def linear_search(arr, target):
    comparisons = 0
    for element in arr:
        comparisons += 1
        if element == target:
            return comparisons  # Return number of comparisons made
    return comparisons

# Binary Search
def binary_search(arr, target):
    comparisons = 0
    left, right = 0, len(arr) - 1
    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

# Perform both searches and count comparisons
linear_comparisons = linear_search(sorted_list, target)
binary_comparisons = binary_search(sorted_list, target)

# Output results
print(f"Linear Search made {linear_comparisons} comparisons.")
print(f"Binary Search made {binary_comparisons} comparisons.")

# Compare the efficiency
if linear_comparisons < binary_comparisons:
    print("Linear Search is more efficient.")
elif binary_comparisons < linear_comparisons:
    print("Binary Search is more efficient.")
else:
    print("Both algorithms made the same number of comparisons.")

Linear Search made 74501 comparisons.
Binary Search made 15 comparisons.
Binary Search is more efficient.

1. Which search algorithm is faster, and why?

Binary Search is faster than Linear Search for large sorted lists because it has a time complexity of O(log n), which means it reduces the search space by half with each comparison. This logarithmic growth makes it much more efficient as the size of the list increases. On the other hand, Linear Search has a time complexity of O(n), which requires checking each element one by one until the target is found, making it slower for larger datasets.

2. What happens if you run both searches on an unsorted list?

  • Linear Search: Will still work correctly on an unsorted list. It simply checks each element in the list one by one, regardless of the order. Its time complexity remains O(n), and it will return the correct result.

  • Binary Search: Will not work correctly on an unsorted list. Since Binary Search assumes that the list is sorted, it relies on dividing the list in half based on the assumption that the elements are ordered. If the list is unsorted, the algorithm may give incorrect results, as it could miss the target or incorrectly divide the list. To use Binary Search, the list must be sorted first, which would add the time complexity of sorting (O(n log n)) before performing the search.