The Computing Series
Foundations of Algorithmic Thinking › Logical Equivalence › Tradeoffs

Tradeoffs

AT4 — Precomputation vs. On-Demand

Logical equivalence enables a fundamental tradeoff: precompute the result of an expression into a simpler form, or evaluate the full expression on demand.

The SQL optimizer precomputes a simplified form of the query. It pays a cost at planning time (the optimization itself) to reduce cost at execution time (fewer operations per row). This is AT4 applied to query evaluation.

In code:

# On-demand: evaluate the full expression every time
def is_eligible_for_discount(user: User, cart: Cart) -> bool:
    return (
        user.account_age_days > 365 and
        user.total_purchases > 500 and
        cart.total > 50 and
        not user.discount_used_this_month
    )

# Precomputed: store an intermediate result
# Trade: cache staleness (FM4) vs. reduced evaluation cost
class User:
    def __init__(self, ...):
        ...
        # Precomputed at user update time — stays valid until account data changes
        self.is_loyal_customer = (
            self.account_age_days > 365 and self.total_purchases > 500
        )

def is_eligible_for_discount_fast(user: User, cart: Cart) -> bool:
    # Uses precomputed result — fewer operations per call
    return user.is_loyal_customer and cart.total > 50 and not user.discount_used_this_month

The second version is logically equivalent to the first for current data. The precomputed is_loyal_customer is a stored truth value. AT4 makes the tradeoff explicit: faster evaluation, but is_loyal_customer can become stale if account data changes without recomputing it. This is the same temporal contract problem from Chapter 1.

# Correct AT4 implementation: invalidation on change
class User:
    def __init__(self, account_age_days: int, total_purchases: float):
        self._account_age_days = account_age_days
        self._total_purchases = total_purchases
        self._is_loyal_customer = self._compute_loyalty()

    def _compute_loyalty(self) -> bool:
        # Single source of truth for loyalty computation
        return self._account_age_days > 365 and self._total_purchases > 500

    @property
    def account_age_days(self) -> int:
        return self._account_age_days

    @account_age_days.setter
    def account_age_days(self, value: int):
        self._account_age_days = value
        self._is_loyal_customer = self._compute_loyalty()  # recompute on change

    @property
    def is_loyal_customer(self) -> bool:
        return self._is_loyal_customer

The precomputed value is always consistent with the underlying data because it is recomputed on change. The AT4 tradeoff is preserved: fast reads, slightly more work on writes.

Read in the book →