Early Termination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# WITHOUT early termination - always processes all elements
def contains_slow(arr, target):
    found = False
    for x in arr:
        if x == target:
            found = True
        # Continues checking even after finding target!
    return found
 
# WITH early termination - stops as soon as answer is known
def contains_fast(arr, target):
    for x in arr:
        if x == target:
            return True  # Immediate exit on first match
    return False
 
# Impact analysis:
# Array: [1, 2, 3, target, 5, 6, ..., 1000000]
# contains_slow: Always 1,000,000 iterations
# contains_fast: Only 4 iterations (stops at index 3)
# Speedup: 250,000x for this case!
 
# The key insight: Once we know the answer, continuing is pure waste.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# Pattern 1: "Does ANY element satisfy condition?" (OR aggregation)
# Short-circuit: Stop on first True
 
def any_positive(numbers):
    """Return True if any number is positive."""
    for n in numbers:
        if n > 0:
            return True  # First positive → entire result is True
    return False  # Checked all, none positive
 
# Pattern 2: "Do ALL elements satisfy condition?" (AND aggregation)  
# Short-circuit: Stop on first False
 
def all_positive(numbers):
    """Return True only if all numbers are positive."""
    for n in numbers:
        if n <= 0:
            return False  # First non-positive → entire result is False
    return True  # Checked all, all positive
 
# Pattern 3: "Find first element satisfying condition"
# Short-circuit: Stop when found
 
def find_first_even(numbers):
    """Return first even number, or None if none exist."""
    for n in numbers:
        if n % 2 == 0:
            return n  # Found it, done
    return None
 
# Pattern 4: "Check if none satisfy condition" (negation)
# Short-circuit: Stop on first True
 
def none_negative(numbers):
    """Return True if no numbers are negative."""
    for n in numbers:
        if n < 0:
            return False  # Found a negative → result is False
    return True
 
# Language-level short-circuiting in Python:
# Python's 'any()' and 'all()' are short-circuit implementations
 
data = [0, 0, 0, 1, 0, 0]  # 1 million more zeros after...
 
# These stop early:
result1 = any(x > 0 for x in data)  # Stops at index 3 (finds 1)
result2 = all(x >= 0 for x in data)  # Stops at first negative (or checks all)
 
# Key: Use generators, not lists, to enable short-circuiting
# This builds entire list first, then checks:
bad = any([expensive_check(x) for x in huge_data])  # All checks run!
 
# This checks lazily and stops early:
good = any(expensive_check(x) for x in huge_data)  # Stops on first True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Scenario: Filter users who are active, verified, and have purchases
 
# BAD: Expensive check first
def get_target_users_slow(users):
    """Runs complex purchase check for ALL users first."""
    return [u for u in users 
            if has_recent_purchases(u)  # Expensive DB query
            and u.is_active              # Cheap attribute check
            and u.is_verified]           # Cheap attribute check
 
# GOOD: Cheap checks first, expensive check last
def get_target_users_fast(users):
    """Cheap checks filter out most users before expensive check."""
    return [u for u in users 
            if u.is_active              # 80% fail here → never check further
            and u.is_verified           # Of remaining, 50% fail here
            and has_recent_purchases(u)]  # Only 10% reach expensive check
 
# Analysis:
# Slow version: 1000 users × expensive_check = 1000 DB queries
# Fast version: 1000 users → 200 active → 100 verified → 100 DB queries
# 10x fewer expensive operations!
 
# For AND conditions: Order by (failure_probability / check_cost)
# High probability of failure + low cost → check first
 
# For OR conditions: Order by (success_probability / check_cost)
# High probability of success + low cost → check first

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

def binary_search_with_early_exit(arr, target):
    """
    Binary search that terminates immediately upon finding target.
    
    Early termination makes best case O(1), average case O(log n),
    worst case O(log n).
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # EARLY TERMINATION: Found it!
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Not found
 
 
def binary_search_leftmost(arr, target):
    """
    Find leftmost (first) occurrence of target.
    
    Here we CANNOT terminate early when finding a match—
    there might be earlier matches. Different problem requires
    different termination strategy.
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid       # Found one, but might not be leftmost
            right = mid - 1    # Keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
 
 
# Key insight: Termination strategy depends on WHAT you're searching for
# - Any occurrence → terminate on first match
# - First/last occurrence → must complete search
# - Count of occurrences → must find boundaries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

from collections import deque
 
def bfs_find_path(graph, start, goal):
    """
    BFS with early termination when goal is reached.
    
    Without early termination: Visits all reachable nodes O(V + E)
    With early termination: Stops as soon as goal is found
    
    For goal close to start, this can be massively faster.
    """
    if start == goal:
        return [start]  # Immediate termination
    
    visited = {start}
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == goal:
                return path + [neighbor]  # EARLY TERMINATION
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path exists
 
 
def dfs_has_path(graph, start, goal, visited=None):
    """
    DFS with early termination on finding goal.
    
    The recursive structure naturally supports early exit:
    returning True propagates up the call stack immediately.
    """
    if visited is None:
        visited = set()
    
    if start == goal:
        return True  # EARLY TERMINATION
    
    visited.add(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            if dfs_has_path(graph, neighbor, goal, visited):
                return True  # Propagate success upward immediately
    
    return False
 
 
# Termination matters for large graphs:
# Graph with 1 million nodes, goal is 2 hops from start
# Full traversal: potentially 1 million node visits
# Early termination: ~10 node visits (depending on branching factor)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

import heapq
 
def branch_and_bound_knapsack(values, weights, capacity):
    """
    0/1 Knapsack with bound-based termination.
    
    Key idea: Compute an upper bound on remaining value.
    If best_so_far >= current + upper_bound_remaining,
    terminate this branch (it cannot beat our best).
    """
    n = len(values)
    
    # Compute value-to-weight ratios for bound calculation
    ratios = [(values[i] / weights[i], i) for i in range(n)]
    ratios.sort(reverse=True)  # Best ratios first
    
    def upper_bound(index, remaining_capacity, current_value):
        """
        Greedy upper bound: What's the max value we could achieve
        from this point, allowing fractional items?
        """
        bound = current_value
        
        for _, i in ratios:
            if i < index:
                continue  # Already decided on this item
            
            if weights[i] <= remaining_capacity:
                bound += values[i]
                remaining_capacity -= weights[i]
            else:
                # Fractional item for bound (not actual solution)
                bound += values[i] * (remaining_capacity / weights[i])
                break
        
        return bound
    
    best_value = 0
    
    # State: (negative_bound, index, current_value, current_weight)
    # Use negative bound for max-heap behavior with min-heap
    heap = [(-upper_bound(0, capacity, 0), 0, 0, 0)]
    
    while heap:
        neg_bound, idx, curr_val, curr_weight = heapq.heappop(heap)
        
        if -neg_bound <= best_value:
            # BOUND-BASED TERMINATION: This branch cannot beat best
            continue
        
        if idx == n:
            best_value = max(best_value, curr_val)
            continue
        
        # Branch: exclude item idx
        exclude_bound = upper_bound(idx + 1, capacity - curr_weight, curr_val)
        if exclude_bound > best_value:
            heapq.heappush(heap, (-exclude_bound, idx + 1, curr_val, curr_weight))
        
        # Branch: include item idx (if it fits)
        if curr_weight + weights[idx] <= capacity:
            new_val = curr_val + values[idx]
            new_weight = curr_weight + weights[idx]
            include_bound = upper_bound(idx + 1, capacity - new_weight, new_val)
            if include_bound > best_value:
                heapq.heappush(heap, (-include_bound, idx + 1, new_val, new_weight))
    
    return best_value
 
# Without bound-based termination: 2^n branches explored
# With bound-based termination: Many branches pruned early
# For tight bounds, exploration can be reduced dramatically

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

def coin_change_with_termination(coins, amount):
    """
    Minimum coins to make amount, with early termination.
    
    Optimization: If we find a solution with k coins where
    k equals the theoretical minimum (amount // max_coin),
    we can terminate immediately - it's optimal.
    """
    if amount == 0:
        return 0
    if not coins:
        return -1
    
    max_coin = max(coins)
    theoretical_min = amount // max_coin  # Best possible
    
    # BFS for shortest path (minimum coins)
    from collections import deque
    
    visited = {0}
    queue = deque([(0, 0)])  # (current_amount, coins_used)
    
    while queue:
        current, num_coins = queue.popleft()
        
        for coin in coins:
            next_amount = current + coin
            
            if next_amount == amount:
                # Found solution
                if num_coins + 1 == theoretical_min:
                    return num_coins + 1  # EARLY TERMINATION: Optimal!
                return num_coins + 1  # BFS guarantees this is optimal anyway
            
            if next_amount < amount and next_amount not in visited:
                visited.add(next_amount)
                queue.append((next_amount, num_coins + 1))
    
    return -1
 
 
def subset_sum_with_bound(nums, target):
    """
    Check if subset sums to target, with bound-based pruning.
    
    Early termination: If remaining elements can't reach target,
    or if current sum already exceeds target, stop.
    """
    nums = sorted(nums, reverse=True)  # Larger elements first for tighter bounds
    
    def backtrack(index, current_sum, remaining_sum):
        if current_sum == target:
            return True  # EARLY TERMINATION: Found it
        
        if index == len(nums):
            return False
        
        # Bound-based termination
        if current_sum > target:
            return False  # EARLY TERMINATION: Exceeded target
        
        if current_sum + remaining_sum < target:
            return False  # EARLY TERMINATION: Can't reach target
        
        # Include or exclude current element
        return (backtrack(index + 1, 
                         current_sum + nums[index], 
                         remaining_sum - nums[index]) or
                backtrack(index + 1, 
                         current_sum, 
                         remaining_sum - nums[index]))
    
    return backtrack(0, 0, sum(nums))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def linear_search_normal(arr, target):
    """
    Standard linear search: 2 comparisons per iteration.
    - Boundary check: i < len(arr)
    - Value check: arr[i] == target
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
 
 
def linear_search_sentinel(arr, target):
    """
    Sentinel-based search: 1 comparison per iteration.
    
    Place target at the end (sentinel), guaranteeing we'll find it.
    Then check if we found the real target or the sentinel.
    
    Roughly 2x faster for failed searches on large arrays.
    """
    n = len(arr)
    if n == 0:
        return -1
    
    # Save last element and place sentinel
    last = arr[n - 1]
    arr[n - 1] = target
    
    i = 0
    while arr[i] != target:
        i += 1
    
    # Restore last element
    arr[n - 1] = last
    
    # Check: did we find real target or sentinel?
    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1
 
 
# For n = 1,000,000 elements, target not present:
# Normal: 2,000,000 comparisons
# Sentinel: 1,000,000 comparisons + minor overhead
# Real-world speedup: significant for comparison-heavy searches
 
# CAUTION: Sentinel requires modifying the array temporarily.
# Not suitable for concurrent access or immutable data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

class ListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev
 
 
class DoublyLinkedListWithSentinels:
    """
    Doubly linked list with sentinel head and tail.
    
    Sentinels eliminate edge case checks:
    - No special case for empty list
    - No special case for inserting at head/tail
    - No null checks when traversing
    """
    
    def __init__(self):
        # Sentinel nodes - not part of actual data
        self.head = ListNode(0)  # Dummy head
        self.tail = ListNode(0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def insert_after(self, node, new_node):
        """
        Insert new_node after node.
        
        WITHOUT sentinels, we'd need:
        - Check if node is None
        - Check if node is the tail
        - Handle empty list case
        
        WITH sentinels: Just do the insertion, no checks needed.
        """
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node
    
    def delete(self, node):
        """
        Delete node from list.
        
        WITHOUT sentinels:
        - Check if node is head (update head pointer)
        - Check if node is tail (update tail pointer)
        - Check if prev/next exist before accessing
        
        WITH sentinels: Simple unlinking, no edge cases.
        """
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def push_front(self, val):
        """Insert at front (after head sentinel)."""
        self.insert_after(self.head, ListNode(val))
    
    def push_back(self, val):
        """Insert at back (before tail sentinel)."""
        self.insert_after(self.tail.prev, ListNode(val))
    
    def pop_front(self):
        """Remove and return first actual element."""
        if self.head.next == self.tail:
            raise IndexError("List is empty")
        node = self.head.next
        self.delete(node)
        return node.val
    
    def __iter__(self):
        """Iterate over actual elements (skip sentinels)."""
        current = self.head.next
        while current != self.tail:
            yield current.val
            current = current.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def fibonacci_eager(n):
    """
    Eager evaluation: Compute all n Fibonacci numbers upfront.
    
    Memory: O(n) for the result list
    Time: O(n) always, even if caller only needs first 5
    """
    fibs = [0, 1]
    for _ in range(n - 2):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs
 
 
def fibonacci_lazy():
    """
    Lazy evaluation: Generate Fibonacci numbers on demand.
    
    Memory: O(1) - only current/previous values stored
    Time: Only computes what's requested
    """
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
 
 
# Usage comparison:
 
# Eager: Must decide count upfront, computes all
fibs_eager = fibonacci_eager(1000000)
first_ten = fibs_eager[:10]  # Computed 1M numbers for 10
 
# Lazy: Computes only what's consumed
fibs_lazy = fibonacci_lazy()
first_ten = [next(fibs_lazy) for _ in range(10)]  # Computed only 10!
 
# Finding first Fibonacci > 1000:
# Eager: Compute many, then search
# Lazy: Stop as soon as condition is met
 
def first_fib_greater_than(threshold):
    """Only compute necessary Fibonacci numbers."""
    for fib in fibonacci_lazy():
        if fib > threshold:
            return fib  # EARLY TERMINATION via lazy evaluation
 
result = first_fib_greater_than(1000)  # Stops at F(17) = 1597

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import itertools
 
def expensive_transform(x):
    """Simulate expensive transformation."""
    print(f"Processing {x}")  # To show what actually runs
    return x * 2
 
def is_special(x):
    """Some filtering condition."""
    return x % 10 == 0
 
# EAGER approach: Transforms ALL data before filtering
def find_first_special_eager(data):
    """Transforms entire dataset even though we need just one result."""
    transformed = [expensive_transform(x) for x in data]  # All processed!
    for item in transformed:
        if is_special(item):
            return item
    return None
 
# LAZY approach: Only transforms until we find what we need
def find_first_special_lazy(data):
    """Stops processing as soon as first special item is found."""
    # map() returns lazy iterator
    transformed = map(expensive_transform, data)
    
    # filter() is also lazy
    specials = filter(is_special, transformed)
    
    # next() triggers lazy evaluation but stops at first result
    return next(specials, None)  # Default None if exhausted
 
 
# Demonstration:
data = list(range(1000))  # [0, 1, 2, ..., 999]
 
# Eager: Processes all 1000 items
result_eager = find_first_special_eager(data)
 
# Lazy: Processes only until finding first multiple of 10
# Output: Processing 0, Processing 1, ..., Processing 5, returns 10
# Only 6 items processed!
result_lazy = find_first_special_lazy(data)
 
 
# itertools provides lazy utilities:
def first_n_primes(n):
    """Generate first n primes lazily."""
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True
    
    # Infinite lazy sequence of primes
    primes = filter(is_prime, itertools.count(2))
    
    # Take only first n
    return list(itertools.islice(primes, n))
 
# Computes exactly n primes, no more

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def bubble_sort_naive(arr):
    """
    Always performs O(n²) comparisons, regardless of input.
    """
    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]
    return arr
 
 
def bubble_sort_optimized(arr):
    """
    Early termination: If no swaps in a pass, array is sorted.
    
    Best case: O(n) for already sorted array
    Worst case: O(n²) unchanged
    Average case: Improved when partially sorted
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:
            break  # EARLY TERMINATION: No swaps means sorted
    
    return arr
 
 
# Impact:
# Already sorted [1, 2, 3, 4, 5]:
# - Naive: 10 comparisons (always)
# - Optimized: 4 comparisons (1 pass, no swaps, exit)
 
# Nearly sorted [1, 2, 3, 5, 4]:
# - Naive: 10 comparisons
# - Optimized: 8 comparisons (2 passes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def insertion_sort(arr):
    """
    Insertion sort naturally terminates early in inner loop.
    
    When inserting element, we stop as soon as we find an element
    smaller than it - we don't scan the entire sorted portion.
    
    This makes insertion sort O(n) for already sorted arrays and
    efficient for nearly sorted data.
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        
        # Inner loop terminates early when correct position found
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key
    
    return arr
 
 
# Already sorted [1, 2, 3, 4, 5]:
# Each element is already in position, inner loop executes 0 times
# Total: O(n) comparisons
 
# Reverse sorted [5, 4, 3, 2, 1]:
# Each element must move to front, inner loop is never terminated early
# Total: O(n²) comparisons
 
# This is why insertion sort is preferred for:
# - Nearly sorted data
# - Small subarrays (used in hybrid sorts like Timsort)
# - Online sorting (elements arriving one at a time)