Knuth optimisation

Why this matters when you build with AI

Interval DP is the method for problems where the answer for a segment is built from answers for two shorter segments inside it. Merging neighbouring blocks in a fixed order, cutting a sequence into parts, and choosing the order of operations on a row of items all have this shape. An AI assistant asked to write one of these usually produces three nested loops: segment length, start point and split point. That is O(n^3) work. For n = 400 the plain version in the test below did 10,666,600 inner steps, and the count grows with the cube of n.

The fast version in this lesson does far fewer steps, but it only gives the right answer when a condition on the cost holds. I tested a cost table with random values and found that 9,496 of 20,000 random tables gave a wrong answer with the fast version, and the program printed the wrong number without any warning. The cost in a real task usually has a clear formula, so the first step is to check that formula against the condition before the speed-up is used.

Terms you need first

Interval [l, r]: the items from position l to position r, counted from 1. An interval of length 1 is a single item.
Interval DP: a table where f[l][r] is the best value for the interval [l, r], built from f values of shorter intervals inside it.
Split point m: the place where [l, r] is cut into [l, m] and [m + 1, r], for some m from l to r - 1.
Cost C(l, r): the extra cost charged when the two parts are joined into [l, r]. The DP total is the sum of these charges over all joins.
Smallest best split opt[l][r]: the smallest m that gives the best value for [l, r]. Using a fixed tie rule is what makes the bound below well defined.
Quadrangle inequality (QI) for intervals: for every a ≤ b ≤ c ≤ d, the rule C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) holds. The lesson on divide and conquer uses the same rule for a different DP form.

The problem and a worked example

I wrote this problem for the lesson. A row of n piles holds a_1 to a_n stones, with every a_i a positive whole number. You may merge two neighbouring piles into one pile. A merge costs the total number of stones in the new pile. Merge the row into a single pile, with the smallest total cost.

The DP is f[l][r] = the smallest total cost to merge piles l to r into one pile. For a single pile, f = 0. For a longer interval, pick the last merge, which joins [l, m] and [m + 1, r]:

f[l][r] = min over m of (f[l][m] + f[m + 1][r] + S(l, r)),

where S(l, r) is the total stones in the interval. Here C(l, r) = S(l, r), the stones in the new pile.

The limits are 1 ≤ n ≤ 400 and 1 ≤ a_i ≤ 1000. The answer fits in a 64-bit integer.

Take the input 4 with piles 4 1 3 2. The prefix sums are S = 0, 4, 5, 8, 10. Here is the table, built one length at a time.

Length 2. f[1][2] = 4 + 1 = 5, with opt = 1. f[2][3] = 1 + 3 = 4, with opt = 2. f[3][4] = 3 + 2 = 5, with opt = 3.
Length 3. f[1][3]: S = 8. Split m = 1 gives f[1][1] + f[2][3] + 8 = 0 + 4 + 8 = 12. Split m = 2 gives f[1][2] + f[3][3] + 8 = 5 + 0 + 8 = 13. Best is 12, opt = 1. f[2][4]: S = 6. Split m = 2 gives 0 + 5 + 6 = 11. Split m = 3 gives 4 + 0 + 6 = 10. Best is 10, opt = 3.
Length 4. f[1][4]: S = 10. Split m = 1 gives 0 + 10 + 10 = 20. Split m = 2 gives 5 + 5 + 10 = 20. Split m = 3 gives 12 + 0 + 10 = 22. The best value 20 is reached at m = 1 and m = 2. The smallest best split is opt = 1.

The answer is 20. The program in the next section prints 20 for this input.

Now the bound. Look at the splits for [1, 4]. The split for [1, 3] is 1, the split for [1, 4] is 1, and the split for [2, 4] is 3. So opt[1][3] = 1 ≤ opt[1][4] = 1 ≤ opt[2][4] = 3. The same pattern holds for every interval. This is Knuth's bound:

opt[l][r - 1] ≤ opt[l][r] ≤ opt[l + 1][r].

Plain meaning: the cut for a longer interval never sits left of the cut for the interval that drops its last item, and never sits right of the cut for the interval that drops its first item. So to find the cut for [l, r], you only scan m from opt[l][r - 1] to opt[l + 1][r], which is usually a short range.

Why the total is O(n^2)

Fix a length len. Write g(x) for the smallest best split of the interval of length len - 1 that starts at x. The scan for the interval starting at l covers m from g(l) to g(l + 1), so the number of steps for that interval is g(l + 1) - g(l) + 1. Add these over every start l for this length. The differences telescope, which means each middle term cancels with the next one. The total is g(last) - g(first) + (number of intervals), and each split value lies between 1 and n. So each length costs at most about n + n steps, and the total over all lengths is O(n^2).

The telescoping is an exact sum, not an estimate. The bound itself is the part that needs the cost to satisfy the inequality, and the proof of the bound is an exchange argument. This lesson gives the idea and does not write the full proof.

Where the bound comes from, and what is known

Knuth's 1971 paper "Optimum binary search trees" in Acta Informatica (volume 1, pages 14 to 25) gives an O(n^2) method for the optimal binary search tree problem, which is an interval DP of this form. Yao's 1980 paper "Efficient dynamic programming using quadrangle inequalities" (STOC 1980) states the quadrangle inequality as the general condition that makes this kind of DP fast. Read both for the proofs. I did not re-derive the full proof here.

What I checked by running code is listed in the next sections. For the linear cost C(l, r) = S(l, r), the condition holds with equality, so the bound holds. For the square cost C(l, r) = S(l, r)^2 on non-negative piles, the same algebra as in the divide and conquer lesson applies, and my tests agreed. For a random cost table, the condition fails, and the bound and the answer both break.

Standard technique with C++17

The file below holds the three parts: a plain interval DP that records the smallest best split, the Knuth version that scans only the bounded range, and a brute-force checker that tests the bound on every interval. It also has a random-table demo and a self-test. The program reads n and then the n piles, and prints the answer.

The program was compiled with g++ -std=c++17 -O2 -Wall -Wextra on g++ 15.2.0. The checks use a fixed random seed, so the numbers below repeat on your machine.

// Interval merge: a row of n piles. Two neighbouring blocks may be merged; a merge costs
// C(l, r), the cost of the merged block (see the cost functions below).
// f[l][r] = min over m of f[l][m] + f[m+1][r] + C(l, r), with f[i][i] = 0.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
 
long long g_brute_iters = 0;
long long g_knuth_iters = 0;
 
// Prefix sums of the piles, 1-based: S[i] = a_1 + ... + a_i.
struct Piles {
    int n;
    vector<ll> S;
    explicit Piles(const vector<ll> &a) : n((int)a.size()), S(a.size() + 1, 0) {
        for (int i = 0; i < n; i++) S[i + 1] = S[i] + a[i];
    }
};
 
// Cost functions take the prefix sums and an interval [l, r] (1-based, l <= r).
ll cost_linear(const Piles &p, int l, int r) { return p.S[r] - p.S[l - 1]; }
ll cost_square(const Piles &p, int l, int r) {
    ll s = p.S[r] - p.S[l - 1];
    return s * s;
}
// Largest pile in the block. This one breaks the quadrangle inequality (see the lesson).
vector<ll> g_piles;
ll cost_max(const Piles &, int l, int r) {
    ll m = 0;
    for (int i = l; i <= r; i++) m = max(m, g_piles[i - 1]);
    return m;
}
 
using CostFn = ll (*)(const Piles &, int, int);
 
// Plain interval DP, O(n^3). Also records the smallest best split for every interval.
struct Result {
    ll value;
    vector<vector<ll>> f;
    vector<vector<int>> opt;
};
 
Result brute_dp(const Piles &p, CostFn C) {
    int n = p.n;
    Result R{0, vector<vector<ll>>(n + 2, vector<ll>(n + 2, 0)), vector<vector<int>>(n + 2, vector<int>(n + 2, 0))};
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            ll best = INF;
            int bestm = l;
            for (int m = l; m < r; m++) {
                g_brute_iters++;
                ll v = R.f[l][m] + R.f[m + 1][r];
                if (v < best) {
                    best = v;
                    bestm = m;
                }
            }
            R.f[l][r] = best + C(p, l, r);
            R.opt[l][r] = bestm;
        }
    R.value = (n >= 1) ? R.f[1][n] : 0;
    return R;
}
 
// Knuth's bound: the split for [l, r] lies between the split for [l, r-1] and the split for [l+1, r].
// Only the bounded search is run, so it costs O(n^2) in total.
Result knuth_dp(const Piles &p, CostFn C) {
    int n = p.n;
    Result R{0, vector<vector<ll>>(n + 2, vector<ll>(n + 2, 0)), vector<vector<int>>(n + 2, vector<int>(n + 2, 0))};
    for (int l = 1; l <= n; l++) R.opt[l][l] = l;  // single pile, no split used
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            int lo = R.opt[l][r - 1], hi = R.opt[l + 1][r];
            // The bound says lo <= hi. If the inputs do not satisfy the inequality, lo can be
            // larger than hi; then the search range is reversed here, and the answer is not guaranteed.
            if (lo > hi) swap(lo, hi);
            ll best = INF;
            int bestm = lo;
            for (int m = lo; m <= hi; m++) {
                g_knuth_iters++;
                ll v = R.f[l][m] + R.f[m + 1][r];
                if (v < best) {
                    best = v;
                    bestm = m;
                }
            }
            R.f[l][r] = best + C(p, l, r);
            R.opt[l][r] = bestm;
        }
    R.value = (n >= 1) ? R.f[1][n] : 0;
    return R;
}
 
// Checks the bound opt[l][r-1] <= opt[l][r] <= opt[l+1][r] for every interval of length >= 3,
// using the brute-force smallest optimal splits. Returns the number of broken bounds.
int bound_violations(const Piles &p, const Result &B) {
    int bad = 0;
    for (int len = 3; len <= p.n; len++)
        for (int l = 1; l + len - 1 <= p.n; l++) {
            int r = l + len - 1;
            if (B.opt[l][r - 1] > B.opt[l][r]) bad++;
            if (B.opt[l][r] > B.opt[l + 1][r]) bad++;
        }
    return bad;
}
 
 
// Random cost table: C(l, r) is an arbitrary value per interval. This does not satisfy the
// quadrangle inequality in general, so it shows what happens when the conditions fail.
vector<vector<ll>> g_table;
ll cost_table(const Piles &, int l, int r) { return g_table[l][r]; }
 
// Random tables: count how often the bound breaks and how often the value is wrong.
// Prints the first case of each kind.
int table_demo() {
    mt19937 rng(11);
    auto rnd = [&](int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); };
    int shownB = 0, shownV = 0;
    long long bound_cases = 0, value_cases = 0, total = 0;
    for (int r = 0; r < 20000; r++) {
        int n = rnd(3, 7);
        g_table.assign(n + 2, vector<ll>(n + 2, 0));
        for (int l = 1; l <= n; l++)
            for (int rr = l; rr <= n; rr++) g_table[l][rr] = rnd(0, 20);
        vector<ll> a(n, 1);
        Piles p(a);
        Result B = brute_dp(p, cost_table);
        Result K = knuth_dp(p, cost_table);
        total++;
        int bv = bound_violations(p, B);
        if (bv > 0) bound_cases++;
        if (B.value != K.value) value_cases++;
        if (bv > 0 && shownB < 1) {
            shownB = 1;
            printf("first broken bound: n=%d, table C(l, r), rows l, columns r:\n", n);
            for (int l = 1; l <= n; l++) {
                for (int c = 1; c <= n; c++) printf(" %3lld", c >= l ? g_table[l][c] : 0LL);
                printf("\n");
            }
            for (int l = 1; l <= n; l++)
                for (int rr = l + 2; rr <= n; rr++)
                    if (B.opt[l][rr - 1] > B.opt[l][rr] || B.opt[l][rr] > B.opt[l + 1][rr])
                        printf("  interval [%d,%d]: opt[l][r-1]=%d opt[l][r]=%d opt[l+1][r]=%d\n", l, rr,
                               B.opt[l][rr - 1], B.opt[l][rr], B.opt[l + 1][rr]);
            printf("  brute value=%lld knuth value=%lld\n", B.value, K.value);
        }
        if (B.value != K.value && shownV < 1) {
            shownV = 1;
            printf("first wrong value: brute=%lld knuth=%lld\n", B.value, K.value);
        }
    }
    printf("random cost tables: %lld of %lld with a broken bound, %lld with a wrong value\n", bound_cases, total,
           value_cases);
    return 0;
}
 
int selftest() {
    mt19937 rng(20261108u);
    auto rnd = [&](int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); };
 
    struct Named {
        const char *name;
        CostFn fn;
    };
    Named costs[] = {{"linear", cost_linear}, {"square", cost_square}};
 
    for (auto &c : costs) {
        int agree = 0, total = 0, bound_bad = 0, bound_cases = 0;
        for (int r = 0; r < 3000; r++) {
            int n = rnd(1, 10);
            vector<ll> a(n);
            for (auto &x : a) x = rnd(1, 20);
            Piles p(a);
            Result B = brute_dp(p, c.fn);
            Result K = knuth_dp(p, c.fn);
            total++;
            if (B.value == K.value) agree++;
            bound_bad += bound_violations(p, B);
            bound_cases++;
        }
        printf("cost=%s: knuth value equals brute value in %d of %d inputs; bound violations %d (inputs %d)\n",
               c.name, agree, total, bound_bad, bound_cases);
    }
 
    // The max-of-block cost: does the bound still hold, and does the answer still match?
    {
        int agree = 0, total = 0, bound_bad = 0;
        for (int r = 0; r < 3000; r++) {
            int n = rnd(1, 10);
            vector<ll> a(n);
            for (auto &x : a) x = rnd(1, 20);
            g_piles = a;
            Piles p(a);
            Result B = brute_dp(p, cost_max);
            Result K = knuth_dp(p, cost_max);
            total++;
            if (B.value == K.value) agree++;
            bound_bad += bound_violations(p, B) > 0 ? 1 : 0;
        }
        printf("cost=max: knuth value equals brute value in %d of %d inputs; inputs with a broken bound %d\n",
               agree, total, bound_bad);
    }
 
    // Work on one fixed input.
    int n = 400;
    vector<ll> a(n);
    for (auto &x : a) x = rnd(1, 1000);
    Piles p(a);
    g_brute_iters = 0;
    g_knuth_iters = 0;
    Result B = brute_dp(p, cost_linear);
    Result K = knuth_dp(p, cost_linear);
    printf("n=%d linear: answer %lld (brute %lld), inner iterations brute=%lld knuth=%lld\n", n, K.value, B.value,
           g_brute_iters, g_knuth_iters);
    return 0;
}
 
int main(int argc, char **argv) {
    if (argc > 1 && string(argv[1]) == "selftest") return selftest();
    if (argc > 1 && string(argv[1]) == "table") return table_demo();
    int n;
    if (!(cin >> n)) return 0;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    Piles p(a);
    printf("%lld\n", knuth_dp(p, cost_linear).value);
    return 0;
}

The worked example gives this output.

$ printf "4\n4 1 3 2\n" | ./knuth
20

The self-test printed this on my machine.

$ ./knuth selftest
cost=linear: knuth value equals brute value in 3000 of 3000 inputs; bound violations 0 (inputs 3000)
cost=square: knuth value equals brute value in 3000 of 3000 inputs; bound violations 0 (inputs 3000)
cost=max: knuth value equals brute value in 3000 of 3000 inputs; inputs with a broken bound 0
n=400 linear: answer 1607914 (brute 1607914), inner iterations brute=10666600 knuth=162633

The cost called max takes the largest pile in the interval as its cost. It did not break in my 3,000 tests with n up to 10, and it did not break in a search over 200,000 random cases with n from 3 to 7 and piles from 1 to 9. That is evidence, not a proof. I do not claim it satisfies the inequality. Treat any cost that you have not checked the same way.

The random-table demo prints the first case where the bound breaks.

$ ./knuth table
first broken bound: n=4, table C(l, r), rows l, columns r:
   9   0  11  17
   0   3   2   3
   0   0  10   8
   0   0   0  19
  interval [1,4]: opt[l][r-1]=2 opt[l][r]=1 opt[l+1][r]=3
  brute value=22 knuth value=25
first wrong value: brute=22 knuth=25
random cost tables: 11463 of 20000 with a broken bound, 9496 with a wrong value

Read the first case closely. In the plain DP, the split for [1, 3] is 2, and the split for [1, 4] is 1, which is left of 2. The bound says that cannot happen. The Knuth scan for [1, 4] runs from 2 to 3, so it misses the true best split at 1, and it returns 25 where the true answer is 22.

Some details matter in the code.

opt[l][l] = l is set before the loops, so the first scan has valid bounds. Without it, the bounds read 0, and the scan would start at split 0, which is not a valid split.
if (lo > hi) swap(lo, hi); runs only when the bound fails. It keeps the loop from running on an empty range. It does not make the answer correct, and the random-table demo shows that.
The plain DP and the Knuth DP both use the rule "smallest best split". The bound checker compares the same values, so a mismatch would show a rule clash.

Complexity

The plain DP does about n^3 / 6 inner steps. For n = 400 the self-test counted 10,666,600, which matches 400^3 / 6 = 10,666,667 closely.

The Knuth version counted 162,633 steps for the same n, which is close to n^2 = 160,000. The count is machine independent, but the running time depends on your machine, so measure it on yours.

Memory is O(n^2). The program keeps two tables of size (n + 2)^2. For n = 5000 that is about 25 million entries, or roughly 300 MB with 8-byte values and 4-byte split indices. Check the limits before you pick the size of the tables.

Common mistakes

Using the bound on a cost that does not satisfy the inequality. The symptom is a wrong answer and no error, as in the table demo, where the value is 25 instead of 22. Check the inequality on the real cost first. In my random-table demo, 9,496 of 20,000 tables gave a wrong answer.
Mixing the two conventions for the split. Some code stores the length of the first part, and some stores the index of the last item of the first part. The bound then compares numbers with different meanings, and the scan range is wrong. Pick one, write it in a comment, and use it in the bound, the DP and the checker.
Forgetting the base case. If opt[l][l] is not set, the first scan starts at 0, which is not a valid split, and the code reads f[l][0] or another index that means nothing here. Reading a value that was never set is undefined behaviour in C++, so the output can change between runs.
Using different tie rules in different places. The bound is stated for a fixed choice of optimal split, here the smallest. If the DP keeps the largest best split and the scan keeps the smallest, the bound can look broken even when the cost is fine. Keep one rule.
Believing the bound from the algebra of a different cost. The square-of-sum cost is one case where the condition holds. A cost with a similar name, such as the square of the length of the interval, is a different function, and it needs its own check.

Hands-on exercise

Work on your own machine in an empty folder.

Save the file from the section above as knuth.cpp, compile it with g++ -std=c++17 -O2 -Wall -Wextra -o knuth knuth.cpp, and run ./knuth selftest and ./knuth table. The numbers should match the output shown, because the seed is fixed. Your running time will differ.
Run the program on the input 3 with piles 2 3 1. Before you run it, work out the answer by hand using the table method from the worked example. Then run it and compare.
Change cost_linear to add a fixed charge of 5 for every merge, so C(l, r) = S(l, r) + 5. Predict first whether the bound still holds for the new cost. The charge adds the same amount to both sides of the inequality, so it cancels. Run ./knuth selftest after the change and check that the bound counts stay at zero.

Prompt to use with an AI reviewer. Paste the code you want reviewed.

Review this Knuth optimisation for interval DP that merges a row of piles.
Check: (1) the initial values for single intervals, and whether any scan can start at an
index outside 1..n; (2) whether the scan range for [l, r] is exactly from opt[l][r-1]
to opt[l+1][r], and what the code does when that range is empty; (3) whether the cost
satisfies the quadrangle inequality for every input the problem allows, and where your
argument uses positive piles. For each claim, say whether you checked it by reading the
code, by a proof, or by running something. Name any claim you could not check.

A good answer separates a proof from a test and names the positive-pile assumption. A weak answer says the bound holds without giving the inequality or a test.

Checklist

Write the cost as C(l, r) and check the quadrangle inequality, by algebra or by a checker over every quadruple.
Choose one split convention and one tie rule, and write both down.
Set the base case for single items before the loops.
Compare the Knuth version with the plain version on random small inputs, with n up to about 10.
Check the bound on every interval of length 3 or more with the plain version's split points.
Estimate the memory from n before you run the program.

Summary

Knuth optimisation cuts the search for each interval's split to the range between the splits of two shorter intervals. The total work is O(n^2), since the ranges telescope along each length. The method is only safe when the cost satisfies the quadrangle inequality, and in my random-table demo a cost table broke the bound in 11,463 of 20,000 trials and the answer in 9,496. Check the cost first, then test the bound and the answer against a brute-force version on small inputs.

Practice

Problem 1. Find the answer for the piles 2 3 1 by hand, with the table method. Then state which split gives it.

Hint: there are two splits for the whole row, and each one needs the value for one shorter interval.

Show the answer

f[1][2] = 2 + 3 = 5 and f[2][3] = 3 + 1 = 4. For the whole row, S = 6. The split m = 1 gives 0 + 4 + 6 = 10. The split m = 2 gives 5 + 0 + 6 = 11. The answer is 10 with split m = 1. The program prints 10 for this input.

Problem 2. Prove the telescoping for one length. Write the sum of the scan sizes for all intervals of length len, and show it is at most about 2n.

Hint: define g(x) as the best split of the interval of length len - 1 starting at x, and write each scan size as g(l + 1) - g(l) + 1.

Show the answer

The scan size for the interval starting at l is g(l + 1) - g(l) + 1. Adding over l from 1 to n - len + 1 gives g(n - len + 2) - g(1) + (n - len + 1). Each g value lies between 1 and n, so the difference is at most n - 1, and the sum is at most about 2n. Over all n lengths the total is at most about 2n^2, which is O(n^2).

Problem 3. Which of these costs satisfy the quadrangle inequality for every a ≤ b ≤ c ≤ d? Give the reason for each. (a) C(l, r) = 1. (b) C(l, r) = (r - l + 1)^2. (c) C(l, r) = the number of distinct values in [l, r].

Hint: for (b), write the cost as a convex function of the interval length. For (c), try the values a = 1, b = 2, c = 2, d = 3 with the values 1, 2, 1.

Show the answer

(a) Holds with equality, since both sides equal 2. (b) Holds. Let x = c - b, y = c - a, z = d - b, w = d - a. Then x + w = y + z, and x ≤ y, z ≤ w. So (y, z) lies between (x, w) in length, and for a convex function of length, f(y) + f(z) ≤ f(x) + f(w). The inequality needs w(a, c) + w(b, d) ≤ w(a, d) + w(b, c), which is f(y) + f(z) ≤ f(w) + f(x). (c) Does not hold in general. Take the values 1, 2, 1 at positions 1 to 3, with a = 1, b = 2, c = 2, d = 3. Then C(1, 2) = 2, C(2, 3) = 2, C(1, 3) = 2, and C(2, 2) = 1. The left side is 4 and the right side is 3. This is one quick counterexample, and it shows the inequality fails.

Problem 4. Describe how to change the program so it prints the best order of merges as a bracketing, for example ((4 1) (3 2)). Say what you store, and what the recursion prints.

Hint: the bracketing for [l, r] uses the split opt[l][r], and the two parts are bracketed in the same way.

Show the answer

The program already stores opt[l][r] for every interval. Write a recursive function that takes l and r. If l == r, it prints the pile. Otherwise it reads m = opt[l][r], prints an open bracket, calls itself on [l, m] and [m + 1, r], and prints a close bracket. For 4 1 3 2 with opt[1][4] = 1, the output starts with the split after the first pile, and the left part [1, 1] is a single pile. The output depends on the tie rule, which here is the smallest best split, so the printed bracketing shows the tie choice.

Problem 5. You want to test the bound on your own cost. Describe the test in a few sentences. Say what it proves and what it does not prove.

Hint: the lesson's bound_violations function compares the split points from the plain DP.

Show the answer

Run the plain DP on many small random inputs, record the smallest best split for each interval, and count any interval of length 3 or more where opt[l][r - 1] > opt[l][r] or opt[l][r] > opt[l + 1][r]. Zero violations on many inputs is evidence the bound holds for that cost on those inputs. It does not prove the bound for all inputs, and it does not prove the inequality. Use the algebra or a quadruple check for the inequality, and use the test to catch a cost that breaks the bound in practice.