Divide and conquer: fast exponentiation, counting inversions, maximum subarray

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Second largest of n elements: minimum comparisons? from Lesson 3.3.3
• Merge sort recurrence and time? from Lesson 3.2.1
• T(n) = T(n/2) + 1? from Lesson 1.2.3

1 · The Hook

🎣

Binary search, merge sort and quicksort share one shape: divide the problem into smaller copies, conquer them recursively, combine the answers. The same shape computes x¹⁰⁰ with 8 multiplications instead of 99, counts inversions in n log n, and finds the best stretch of profits in a list.

2 · Predict First

🤔

To compute x¹⁶, the obvious way multiplies 15 times. How few multiplications suffice if you may reuse results (x², x⁴, …)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

4: x² = x·x, x⁴ = x²·x², x⁸ = x⁴·x⁴, x¹⁶ = x⁸·x⁸. In general about log n.

The paradigm

• Divide the instance into a subproblems of size n/b.
• Conquer each recursively (small ones directly).
• Combine their answers in f(n) time.

Running time: T(n) = aT(n/b) + f(n), solved by the master theorem (Lesson 1.2.3).

Fast exponentiation

xⁿ = (x^⌊n/2⌋)², times x once more if n is odd.

long power(long x, int n) {
    if (n == 0) return 1;
    long h = power(x, n / 2);
    return (n % 2) ? h * h * x : h * h;
}

T(n) = T(n/2) + c → Θ(log n) multiplications. Counting (with x¹ needing none): x¹⁵ needs 6, x¹⁶ needs 4, x¹⁰⁰ needs 8.

Counting inversions (merge sort with a counter)

While merging the sorted halves L and R, every time an element of R is output before the remaining elements of L, it forms an inversion with each remaining element of L: add (number of elements left in L). Total time Θ(n log n) instead of the Θ(n²) pair check.

Maximum subarray sum

Find the contiguous stretch with the largest sum. Divide and conquer: the best subarray is entirely in the left half, entirely in the right half, or crosses the middle (best suffix of the left + best prefix of the right, found in Θ(n)). T(n) = 2T(n/2) + Θ(n) → Θ(n log n). (A one-pass method, Kadane's algorithm, does it in Θ(n); it is dynamic programming, Phase 5.)

Example: [−2, 1, −3, 4, −1, 2, 1, −5, 4] → best stretch [4, −1, 2, 1] with sum 6.

4 · Visual

x^13 by halving:   13 -> 6 -> 3 -> 1
x^1 = x
x^3  = (x^1)^2 * x      2 multiplications
x^6  = (x^3)^2          1
x^13 = (x^6)^2 * x      2           total 5

5 · Worked Examples

Example 1 Easy

Multiplications to compute x³² by repeated squaring?

Solution

32 → 16 → 8 → 4 → 2 → 1: 5 squarings.

Example 2 Medium

Multiplications to compute x¹⁵ with the recursive method above?

Solution

x³ (2), x⁷ = (x³)²·x (2), x¹⁵ = (x⁷)²·x (2): 6.

Example 3 GATE

Maximum subarray sum of [−3, 2, 5, −1, 6, −4, 1]?

Solution

[2, 5, −1, 6] = 12.

6 · GATE Traps

⚠️

• Each odd step in fast exponentiation costs one extra multiplication.
• The crossing case must use both sides of the middle.
• Counting inversions adds the number of remaining left elements, not 1.
• D&C maximum subarray is Θ(n log n); the linear method is a different idea.

7 · Memory Hook

🧠

"Divide, conquer, combine: the combine step sets f(n)."

8 · Connect the Dots

Phase 3 sorted by divide and conquer; this lesson used the paradigm beyond sorting. Next: splitting numbers and matrices so that fewer than the obvious number of multiplications are needed (Karatsuba and Strassen).

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markSquaring

Multiplications to compute x⁶⁴ by repeated squaring?

Numerical answer: ________

Q2NAT2 marksOdd exponent

Multiplications to compute x³¹ with the recursive method (square, plus one extra multiply on odd n)?

Numerical answer: ________

Q3NAT2 marksMax subarray

Maximum subarray sum of [2, −1, 3, −4, 5, −2, 1]?

Numerical answer: ________

Q4MCQ1 markRecurrence

Divide-and-conquer maximum subarray runs in:

• (A) Θ(n)
• (B) Θ(n log n)
• (C) Θ(log n)
• (D) Θ(n²)

Q5MCQ1 markInversion counting

Counting inversions with a modified merge sort takes:

• (A) Θ(log n)
• (B) Θ(n)
• (C) Θ(n²)
• (D) Θ(n log n)

10 · Rule Card

• D&C: divide into a pieces of size n/b, conquer, combine in f(n): T = aT(n/b) + f(n).
• Fast power: Θ(log n) multiplications (squarings + one per odd step).
• Inversions via merge: add remaining-left count; Θ(n log n).
• Max subarray D&C: left, right, crossing; Θ(n log n).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

divide, conquer, combinefast exponentiation by squaringmultiplications for xⁿcounting inversions by mergingmaximum subarray (crossing case)

12 · Answer Vault