Algorithm Analysis and Divide & Conquer: Rethinking Algorithms

How can we mathematically predict an algorithm’s efficiency before executing it, and when does dividing a problem make it faster?

Explore the foundations of algorithm analysis, asymptotic complexity, and divide-and-conquer design through recursive problem decomposition and the Maximum Subsequence Sum problem.

The easiest way to find a maximum is to keep the largest value seen so far. That intuition is almost irresistible. Read a number, compare it with the current maximum, and ✨move on✨

Unfortunately, the maximum subsequence problem is not asking for the largest number. It asks for the largest sum of consecutive numbers. A negative value can lower the sum without ending the best sequence, and a seemingly excellent answer can become the wrong one a few elements later.

That small distinction is enough to turn a simple scan into a much more interesting question:

What work must an algorithm do to be certain its answer is correct?

The Maximum Subsequence Problem: Why Stopping at 22 Feels Right

Consider the sequence:

We must choose a starting index ( i ) and an ending index ( j ), keeping every element between them. The objective is:

This is a contiguous subsequence: we cannot quietly discard an inconvenient value in the middle. For now, a candidate contains at least one element.

The pair (10,12) gives (22). A perfectly reasonable first thought is to stop there. Adding (-5) reduces the total to (17); adding (-7) reduces it further to (10). Why would the optimal sequence willingly get worse?

Because the sequence has not finished speaking.

The actual maximum is 23 , from index 2 through index 8 with one-based indexing. The local peak of 22 was real. It simply wasn’t the global answer.

The trap is not that the first intuition was foolish. It is that a temporary decrease provides no proof about what comes afterward.

So the safe first design is obvious: inspect every possible interval.

---

A Correct Answer With a Cubic Price Tag

Choose every starting position i. For each start, choose every possible ending position j ≥ i. Then calculate the sum of that interval from scratch.

best = -infinity

for i = 1 to n:
    for j = i to n:
        current = 0
        for k = i to j:
            current = current + X[k]
        best = max(best, current)

This method is correct because no contiguous interval escapes it. But correctness has acquired a cost: the algorithm repeatedly adds values it has already added.

The precise number of array-element additions performed by the innermost loop is:

Why _j - i + 1 _? Because an interval from position i to position j contains both endpoints. Positions 4,5,6,7,8 , for example, contain five elements, not four.

We can derive the total rather than merely counting three loops and guessing:

![[\begin{aligned} W(n) &=\sum_{i=1}^{n}\frac{(n-i+1)(n-i+2)}{2}\[4pt] &=\frac12\sum_{r=1}^{n}r(r+1)\[4pt] &=\frac12\left(\sum_{r=1}^{n}r²+\sum_{r=1}^{n}r\right)\[4pt] &=\frac12\left(\frac{n(n+1)(2n+1)}6+\frac{n(n+1)}2\right)\[4pt] &=\boxed{\frac{n(n+1)(n+2)}6}. \end{aligned} ]](https://cdn-images-1.medium.com/max/516/0*_AQaZdUGaVdAaI8d.png)

That is an exact count of the innermost additions, not an exact measurement of wall-clock execution time. Other operations have their own costs. But its dominant term is n³/6 , so the algorithm runs in:

The Θ notation describes a tight asymptotic growth rate: for sufficiently large n , runtime is bounded above and below by constant multiples of n³. The constant 1/6 matters to the exact count but not to the asymptotic class.

The uncomfortable part is that we have not made a bad choice of candidates. We are doing too much work per candidate.

---

Remember One Sum, Remove One Loop

Suppose the sum from i through j is already known. To extend it by one element, why start again at i ?

That single identity removes the innermost loop. Fix a start, maintain a running sum, and extend the end one position at a time.

best = -infinity

for i = 1 to n:
    current = 0
    for j = i to n:
        current = current + X[j]
        best = max(best, current)

Now each candidate requires only an addition and a comparison, both constant-time operations in the usual algorithmic cost model. The number of interval endpoints we inspect is:

Therefore:

From cubic to quadratic, just by refusing to recalculate a sum we already know. A surprisingly large improvement for such a modest change.

But two loops remain because we still try every starting position. Could we avoid that too?

First, there is a boundary we cannot avoid. If an algorithm never reads some element X[k], that unseen element could be an arbitrarily large positive value. The claimed maximum might then be wrong. In the worst case, every element must be inspected:

The target is now visible. We cannot reasonably expect sublinear time for arbitrary input, but quadratic time is not the limit either.

We need a design that stops treating every (i,j) pair as a separate question.

---

Divide and Conquer: A Split That Loses the Answer

A familiar idea presents itself to The Origami Software Engineer:

Divide a length- n sequence into two halves, solve each half recursively, and take the larger answer.

A split can be valuable because smaller inputs are often disproportionately cheaper. If an n² computation could become two independent computations on n/2 elements, their combined cost would be:

Tempting. But splitting is not free, and it does not guarantee the halves contain everything we need. The number of subproblems, their sizes, and the cost of combining them all matter.

For maximum subsequence sum, the naive combination is:

It looks plausible until the optimal interval begins in L and ends in R. In our eight-element example, the maximum interval runs from 10 to the final 2 , crossing the boundary between -5 and -7.

The answer is in neither half. Each half is correct about its own input, yet the parent can still be wrong.

Every contiguous interval lies entirely in the left half, entirely in the right half, or crosses the midpoint. Those cases are exhaustive.

So the recurrence for the answer must be:

where m=|_(i+j)/2_| and C is the best interval crossing that boundary.

The split was fine. The combination rule was incomplete.

---

The Crossing Case: Correct but Still Expensive

The obvious repair is to enumerate crossing intervals. Start somewhere in the left half, end somewhere in the right half, and retain the largest sum. As with the quadratic running-sum method, partial sums can be maintained while the right endpoint moves.

With approximately n/2 choices for each endpoint, the combination work is proportional to:

We now have two recursive calls and a quadratic combination step:

To understand its cost, look at how much work occurs across each recursion level. At depth l , there are 2^l subproblems, each of size approximately n/2^l :

The level costs form a geometric series:

So recursion has not saved us from quadratic time. The smaller calls are cheaper, but the parent insists on checking too many crossing candidates.

This is where divide and conquer starts to look less like a trick for splitting arrays and more like a discipline for designing the information returned by a subproblem.

---

Scan From the Boundary, Not From Everywhere

Consider any interval that crosses the midpoint. Its left portion must end at m , and its right portion must begin at m+1.

That changes what we need to search.

Instead of trying every left start against every right end, find just two things:

• The maximum-sum suffix ending at m.
• The maximum-sum prefix beginning at m+1.

Then add them:

Both portions are nonempty here, because we are explicitly calculating a crossing interval.

One scan travels left from the midpoint; another travels right from the next position. Each keeps its best running sum. Together they inspect at most (n) elements, so the combination is Θ(n), not Θ(n²).

The new recurrence is:

This time, each recursion level performs roughly the same total amount of work:

The number of levels is proportional to log_2 n , so:

We have gone from quadratic to n log n by changing only the way we compute the crossing answer.

And yet the same question returns:

Why scan those elements again at the parent if the children have already examined them?

---

Four Numbers That Make the Merge Constant-Time

A child that returns only its maximum subsequence sum is withholding information its parent needs. In particular, the parent must somehow recover the child’s best boundary-touching intervals to evaluate a crossing sequence.

So let each recursive call return four values , not one:

• Sum  — the sum of every element in its interval.
• Max  — the best contiguous subsequence anywhere inside it.
• Lmax  — the best prefix, beginning at its left boundary.
• Rmax  — the best suffix, ending at its right boundary.

The names matter because the merge is built from exactly these meanings. For a single element v , all four are simply v.

Written mathematically, for left child L , right child R , and parent _P _ :

![\begin{aligned}
P.\mathrm{Sum} &=L.\mathrm{Sum}+R.\mathrm{Sum},\[3pt]
P.\mathrm{Lmax}&=\max\big(L.\mathrm{Lmax},\ L.\mathrm{Sum}+R.\mathrm{Lmax}\big),\[3pt]
P.\mathrm{Rmax}&=\max\big(R.\mathrm{Rmax},\ R.\mathrm{Sum}+L.\mathrm{Rmax}\big),\[3pt]
P.\mathrm{Max}&=\max\big(L.\mathrm{Max},\ R.\mathrm{Max},\ L.\mathrm{Rmax}+R.\mathrm{Lmax}\big)
\end{aligned}](https://cdn-images-1.medium.com/max/648/0*m_G1c-onHkFTYvPe.png)

Each formula follows from a boundary constraint. The best prefix either stays within L or consumes all of L and continues into a prefix of R. The best suffix is symmetric. The global maximum is left-only, right-only, or crossing; in the crossing case it must join a suffix of L to a prefix of R.

Nothing else needs to be carried upward. No loop is needed to combine the four values.

Here is the full recursive algorithm in Python-like form:

def maximum_subsequence(x):
    def solve(lo, hi):
        if lo == hi:
            v = x[lo]
            return v, v, v, v # Sum, Max, Lmax, Rmax

        mid = (lo + hi) // 2
        sum_l, max_l, lmax_l, rmax_l = solve(lo, mid)
        sum_r, max_r, lmax_r, rmax_r = solve(mid + 1, hi)

        total = sum_l + sum_r
        lmax = max(lmax_l, sum_l + lmax_r)
        rmax = max(rmax_r, sum_r + rmax_l)
        best = max(max_l, max_r, rmax_l + lmax_r)
        return total, best, lmax, rmax

    if not x:
        raise ValueError("Expected a nonempty sequence")

    return solve(0, len(x) - 1)[1]

The implementation returns the maximum sum. If the actual start and end indices are also required, the selected interval boundaries can accompany the summary values; the same three-way correctness argument still applies.

---

The Worked Merge: The Answer Was Crossing All Along

Return to the original sequence and split it after the fourth element:

The left child’s four-value summary is:

The right child’s summary is:

Notice what the boundary values remember. The left suffix [10,12,-5] sums to 17. The right prefix [-7,8,3,2] sums to 6. Neither looks especially heroic in isolation. Joined across the midpoint, they become the best interval.

Now compute the parent without scanning the original sequence:

The same value that defeated the tempting local answer appears from one addition and a three-way comparison at the merge. We didn’t guess the winning interval. We kept precisely the information needed to prove we hadn’t missed it.

That changes the runtime one final time:

One way to see the bound is to count the work across a balanced recursion tree. The number of subproblems doubles as their size halves:

Each subproblem combines a constant number of values, so the total work is O(n). And since every input element must be examined in the worst case, the Ω(n) lower bound matches it. The result is therefore Θ(n). The recursion uses O(log n) stack space for balanced splits; each call returns only a constant-size summary.

---

What Actually Changed?

All five designs were trying to answer the same question. Each one removed a different kind of unnecessary work:

The important detail is that the final three divide-and-conquer versions split the input in essentially the same way. Two recursive calls, each handling approximately half the sequence. Yet they produce different growth rates because they pay different prices to combine their answers:

Divide and conquer is not a promise that splitting a problem will make it faster. It is a request to examine what each half can establish, what the parent still needs, and what it costs to bridge that gap.

Initially, the parent knew only each child’s maximum and had to do the crossing work itself. Eventually, the children returned enough boundary information that the parent could combine their results immediately. The solution did not emerge from a more aggressive split. It emerged from a better understanding of the dependency across the split.

The first algorithm wasn’t wrong. Its model of necessary work was simply too generous. One redundant sum disappeared, then a redundant pair of endpoints, then a redundant scan. What remained was the work the input itself demanded.

That’s not failure.

That’s evolution.

---

The “I liked this” Starter Pack:

Don’t let your fingers get lazy now.

• Like : It tells me this was worth writing.
• A Comment: Tell me your thoughts, your favorite snack, or a better title for this blog.
• Boost it: Especially with that one developer who definitely needs this.

Thanks for being here. It genuinely helps more than you know!

— Aaroophan Varatharajan

Find me elsewhere:

• Professional stuff: linkedin.com/in/Aaroophan
• Code stuff: github.com/Aaroophan
• UI stuff: aaroophan.dev/Aaroophan
• Life stuff: instagram.com/Aaroophan