Recursive algorithms

Part 5 · Recursion · Chapter 17 · Lecture notes, volume 5 (PDF) · Exercises: Recursive algorithms · App: Merge sort

Introduction

In the chapters «Recursion», «Recurrences» and «The Master Theorem» we have learnt how a recursive algorithm is executed, how its number of steps is described by a recurrence, and how such a recurrence is solved. In this chapter we put these tools to work on four classical problems on arrays:

• the sum of the elements of an array, the simplest possible problem, on which we compare an iterative and two recursive algorithms;

• sorting, with Merge Sort, the first algorithm of the course that beats the \(\Theta(n^2)\) sorting algorithms;

• searching in a sorted array, with the Recursive Binary Search;

• the maximum subarray problem, where a divide and conquer algorithm improves on brute force, and a clever iterative algorithm improves on both.

All the algorithms are studied with the same scheme, which is the scheme of the analysis of every recursive algorithm.

For each recursive algorithm we:

1. write the pseudo-code and run it on a small example, drawing the call tree;

2. prove that it is correct, by (strong) induction on the size of the sub-problem;

3. describe its number of steps by a recurrence and solve it, with the recursion tree and with the Master Theorem;

4. express the worst-case running time as a function of the input size \(|I|\);

5. measure the extra memory, which for a recursive algorithm includes the call stack;

6. run it in Python, C++ and Java, in the Colab notebooks of the chapter (arrays indexed from \(0\), while in the pseudo-code they are indexed from \(1\)).

Three of the four algorithms follow the divide and conquer paradigm: the problem on a sub-array \(a[l..r]\) is split into sub-problems on the two halves \(a[l..m]\) and \(a[m+1..r]\) (divide), the sub-problems are solved recursively (conquer), and their solutions are put together (combine). The Recursive Binary Search, instead, makes a single recursive call on one half.

17.1 The sum of the elements of an array

17.1.1 The problem

Given an array \(a[1..n]\) of \(n \ge 1\) integer numbers, we consider the problem of computing the sum of its elements:

\[ \sum_{i=1}^{n} a[i] = a[1]+a[2]+\cdots+a[n]. \]

• This is one of the simplest problems on arrays, and it is the ideal problem to compare an iterative algorithm and a recursive algorithm that solve the same problem.

• We write the recursive algorithm, we prove that it is correct, we describe its number of steps by a recurrence and we solve the recurrence, using the tools of the chapters «Recursion», «Recurrences» and «The Master Theorem».

Example 17.1: sum of an array

We consider the following array of \(n=7\) integer numbers:

\[ \begin{array}{c|c|c|c|c|c|c|c|} {a[i]} & {i=1} & {i=2} & {i=3} & {i=4} & {i=5} & {i=6} & {i=7} \\ & 9 & 8 & 12 & 3 & 5 & 14 & 6 \end{array} \]

The sum of its elements is

\[ 9+8+12+3+5+14+6 = 57. \]

17.1.2 Iterative algorithm

• We start from the obvious iterative algorithm SumIterative, which scans the array from left to right and accumulates the partial sums in the variable \(s\):

Algorithm: SumIterative

Input: An array \(a[1..n]\) of \(n\) integer numbers

Output: The sum \(a[1]+a[2]+\cdots+a[n]\)

1function SumIterative(a, n)

2\(s := 0\)

3\(i := 1\)

4while \(i \le n\) do

5\(s \leftarrow s + a[i]\)

6\(i \leftarrow i + 1\)

7end

8return \(s\)

9end

Run in Colab:PythonC++Java

• Let \(S(n)\) denote the number of steps executed by SumIterative on an array of \(n\) elements (there is no difference between best and worst case: the algorithm always performs the same operations). The number of times each line of code is executed is:

  • Line 2 is executed \(1\) time

  • Line 3 is executed \(1\) time

  • Line 4 is executed \(n+1\) times

  • Line 5 is executed \(n\) times

  • Line 6 is executed \(n\) times

  • Line 8 is executed \(1\) time

  Therefore,

  \[ S(n) = 1+1+(n+1)+n+n+1 = 3n+4 = \Theta(n), \qquad\text{since}\qquad \lim_{n\to\infty}\frac{3n+4}{n}=\lim_{n\to\infty}\left(3+\frac{4}{n}\right)=3\in\R_{>0}. \]

• Besides the input array, the algorithm uses only the two variables \(s\) and \(i\): the extra memory is \(\Theta(1)\).

17.1.3 Recursive algorithm (divide and conquer)

• The same sum can be computed recursively. The sum of the elements of a sub-array \(a[l..r]\) is obtained by divide and conquer:

  1. Divide: split \(a[l..r]\) in two halves \(a[l..m]\) and \(a[m+1..r]\), where \(m=\lfloor (l+r)/2\rfloor\);

  2. Conquer: compute recursively the sum \(s_1\) of \(a[l..m]\) and the sum \(s_2\) of \(a[m+1..r]\);

  3. Combine: return \(s_1+s_2\).

• The base case is a sub-array with a single element (\(l=r\)): its sum is the element \(a[l]\) itself.

• This is the pseudo-code of the recursive algorithm RecursiveSum. To sum the whole array we call RecursiveSum\((a,1,n)\).

Algorithm: RecursiveSum

Input: An array \(a\) and two indices \(l \le r\)

Output: The sum \(a[l]+a[l+1]+\cdots+a[r]\)

1function RecursiveSum(a, l, r)

2if \(l = r\) then

3return \(a[l]\)// Base case

4end

5\(m := \lfloor (l+r)/2 \rfloor\)// Divide

6\(s_1 :=\) RecursiveSum\((a, l, m)\)// Conquer (left half)

7\(s_2 :=\) RecursiveSum\((a, m+1, r)\)// Conquer (right half)

8return \(s_1 + s_2\)// Combine

9end

Run in Colab:PythonC++Java

• Let \(k = r-l+1\) be the number of elements of \(a[l..r]\). If \(k\ge 2\), the two halves have

  \[ m-l+1 = \left\lceil \frac{k}{2}\right\rceil \qquad\text{and}\qquad r-m = \left\lfloor \frac{k}{2}\right\rfloor \]

  elements, respectively. Both numbers are at least \(1\) and strictly smaller than \(k\): every recursive call works on a smaller sub-array, and the recursion always reaches the base case.

17.1.4 Call tree

• The execution of a recursive algorithm is represented by its call tree: every node is a call, and the children of a node are the calls it makes. The value returned by a call is sent back to its parent.

Example 17.2: call tree of RecursiveSum

We consider the array of Example 17.1, i.e., \(a=[9,8,12,3,5,14,6]\) and \(n=7\). This is the call tree of RecursiveSum\((a,1,7)\), where each node RS\((l,r)\) is a call on the sub-array \(a[l..r]\). In blue the elements of the array returned by the base cases, in red the values returned by the calls to their parents (along the arrows):

• The root RS\((1,7)\) computes \(m=\lfloor 8/2\rfloor = 4\) and calls RS\((1,4)\) and RS\((5,7)\).

• RS\((1,4)\) computes \(m=2\) and returns \(17+15=32\); RS\((5,7)\) computes \(m=6\) and returns \(19+6=25\).

• The root returns \(32+25=57\), which is the sum of the elements of the array.

• There are \(13 = 2\cdot 7-1\) calls: \(7\) leaves (base cases, one for each element) and \(6\) internal nodes, each of which performs one addition, so there are \(6=n-1\) additions in total.

• The calls are executed in depth-first order: a call is completed only after both its children are completed. In the example the calls terminate in the order

  \[ (1,1),\ (2,2),\ (1,2),\ (3,3),\ (4,4),\ (3,4),\ (1,4),\ (5,5),\ (6,6),\ (5,6),\ (7,7),\ (5,7),\ (1,7). \]

17.1.5 Correctness

• The correctness of a recursive algorithm is proved by strong induction on the size of the sub-problem: we assume that the recursive calls, which work on smaller sub-arrays, are correct, and we show that the call combines their results correctly.

Observation 17.1: correctness of RecursiveSum

For every pair of indices \(l \le r\), the call RecursiveSum\((a,l,r)\) terminates and returns

\[ \sum_{i=l}^{r} a[i]. \]

Proof

We use strong induction on the number \(k=r-l+1 \ge 1\) of elements of the sub-array.

Base case (\(k=1\)). Then \(l=r\), the condition of line 2 is true and the algorithm returns \(a[l] = \sum_{i=l}^{l} a[i]\).

Inductive step (\(k \ge 2\)). Assume that the statement holds for all sub-arrays with fewer than \(k\) elements (inductive hypothesis). Since \(l<r\), the algorithm computes \(m=\lfloor (l+r)/2\rfloor\), with \(l \le m < r\). The sub-arrays \(a[l..m]\) and \(a[m+1..r]\) have \(\lceil k/2\rceil\) and \(\lfloor k/2\rfloor\) elements, both between \(1\) and \(k-1\). By the inductive hypothesis, the two recursive calls terminate and

\[ s_1 = \sum_{i=l}^{m} a[i], \qquad s_2 = \sum_{i=m+1}^{r} a[i]. \]

Therefore, the algorithm returns

\[ s_1+s_2 = \sum_{i=l}^{m} a[i] + \sum_{i=m+1}^{r} a[i] = \sum_{i=l}^{r} a[i]. \]

□

• With \(l=1\) and \(r=n\), the call RecursiveSum\((a,1,n)\) returns the sum of all the elements of the array.

17.1.6 Number of steps of RecursiveSum

The recurrence

• Let \(S(n)\) denote the number of steps executed by RecursiveSum on a sub-array of \(n=r-l+1\) elements. As for the iterative algorithm, the number of steps depends only on \(n\) (and not on the values of the elements).

• We count the lines of code executed by a single call. A line containing a recursive call counts as \(1\) step (the call itself) plus all the steps executed by the called function, which we express again using \(S\).

• If \(n=1\), lines 2 and 3 are executed \(1\) time each, and therefore \(S(1)=2\).

• If \(n\ge 2\):

  • Line 2 is executed \(1\) time

  • Line 3 is not executed

  • Line 5 is executed \(1\) time

  • Line 6 is executed \(1\) time, plus the \(S(\lceil n/2\rceil)\) steps of the call on \(a[l..m]\)

  • Line 7 is executed \(1\) time, plus the \(S(\lfloor n/2\rfloor)\) steps of the call on \(a[m+1..r]\)

  • Line 8 is executed \(1\) time

  and therefore \(S(n) = S(\lceil n/2\rceil)+S(\lfloor n/2\rfloor)+5\).

The number of steps of RecursiveSum is described by the recurrence

\[ S(n)= \begin{cases} 2 & \text{if } n=1,\\[1mm] S\big(\lceil n/2\rceil\big)+S\big(\lfloor n/2\rfloor\big)+c & \text{if } n\ge 2, \end{cases} \]

with \(c=5\). As usual, in the asymptotic analysis we write it simply as

\[ S(n) = 2\,S(n/2) + c . \]

Solution with the recursion tree

• In the recursion tree every node represents a call and contains the number of steps executed by that call excluding the steps of its recursive calls: \(c\) for an internal node, \(2\) for a leaf. \(S(n)\) is the sum of the values of all the nodes.

• For simplicity, assume first that \(n=2^h\) is an exact power of \(2\). Then every sub-array is split into two halves of equal size, and the tree is:

• Level \(i\) contains \(2^i\) calls on sub-arrays of \(n/2^i\) elements. The leaves are at level \(\log_2 n\), where the sub-arrays have \(n/2^{\log_2 n}=1\) element: there are \(2^{\log_2 n}=n\) leaves.

• The internal levels \(0,1,\dots,\log_2 n-1\) contain

  \[ \sum_{i=0}^{\log_2 n-1} 2^i = 2^{\log_2 n}-1 = n-1 \]

  nodes (sum of a geometric series). Therefore the total number of steps is

  \[ S(n) = c\,(n-1) + 2n = 5(n-1)+2n = 7n-5. \]

• The cost of the levels doubles from one level to the next one: the total is dominated by the leaves, which are \(n\). This is exactly the situation of case 1 of the Master Theorem.

• The same counting holds for every \(n\), not only for powers of \(2\): the key fact is that the tree has exactly \(n\) leaves and \(n-1\) internal nodes, as the next observation shows.

Observation 17.2: calls and steps of RecursiveSum

For every \(n\ge 1\), the call RecursiveSum\((a,l,r)\) on a sub-array of \(n=r-l+1\) elements generates exactly

\[ 2n-1 \]

calls (including the first one): \(n\) of them are base cases and \(n-1\) of them perform one addition. Moreover, \(S(n)=7n-5\).

Proof

Let \(C(n)\) be the number of calls. We have \(C(1)=1\) and, for \(n\ge 2\),

\[ C(n) = 1 + C(\lceil n/2\rceil) + C(\lfloor n/2\rfloor). \]

We prove \(C(n)=2n-1\) by strong induction on \(n\). For \(n=1\): \(C(1)=1=2\cdot 1-1\). For \(n \ge 2\), by the inductive hypothesis applied to \(\lceil n/2\rceil<n\) and \(\lfloor n/2\rfloor<n\),

\[ C(n) = 1 + \big(2\lceil n/2\rceil-1\big) + \big(2\lfloor n/2\rfloor-1\big) = 2\big(\lceil n/2\rceil+\lfloor n/2\rfloor\big) - 1 = 2n-1, \]

because \(\lceil n/2\rceil+\lfloor n/2\rfloor=n\) for every natural number \(n\).

Each base case corresponds to exactly one element of the sub-array (the sub-arrays of the leaves are disjoint and cover \(a[l..r]\)), so there are \(n\) base cases and \(2n-1-n=n-1\) calls that execute line 8.

In the same way, \(S(1)=2=7\cdot 1-5\) and, for \(n\ge 2\),

\[ S(n) = \big(7\lceil n/2\rceil-5\big) + \big(7\lfloor n/2\rfloor-5\big) + 5 = 7n-5. \]

□

• Accordingly,

  \[ S(n)=7n-5=\Theta(n), \qquad\text{since}\qquad \lim_{n\to\infty}\frac{7n-5}{n}=7\in\R_{>0}. \]

  For the array of Example 17.2, \(S(7)=44\): \(7\) leaves with \(2\) steps each and \(6\) internal nodes with \(5\) steps each.

Solution with the Master Theorem

• We can obtain the order of growth of \(S(n)\) directly from the Master Theorem, without computing \(S(n)\) exactly. We recall case 1 of the Master Theorem:

Let \(S(n)=a\,S(n/b)+f(n)\), with \(a\ge 1\) and \(b>1\) constants and \(f(n)\) asymptotically positive. If \(f(n)=O\big(n^{\log_b a-\varepsilon}\big)\) for some constant \(\varepsilon>0\), then

\[ S(n)=\Theta\big(n^{\log_b a}\big). \]

• \(S(n)=2\,S(n/2)+c\) \(\quad\rightarrow\quad\) \(a=2\), \(b=2\), \(f(n)=c\).

• \(n^{\log_b a}=n^{\log_2 2}=n^1=n\).

• Comparison: \(f(n)=c\) grows polynomially slower than \(n\) \(\quad\rightarrow\quad\) case 1.

• Hypothesis: \(f(n)=c=O\big(n^{1-\varepsilon}\big)\) with \(\varepsilon=1\), since \(c = c\cdot n^{0}\).

• Conclusion: \(S(n)=\Theta\big(n^{\log_2 2}\big)=\Theta(n)\).

As expected, the result agrees with the exact solution \(S(n)=7n-5\).

Worst-case running time

• As in the chapter «Running time», we make the hypothesis that every entry of the array is stored using a fixed constant number of bits. Then \(|I|=\Theta(n)\), i.e., there exist constants \(c_1,c_2>0\) such that \(c_1 n\le |I| \le c_2 n\) for all sufficiently large \(n\), and

  \[ \frac{1}{c_2}|I| \le n \le \frac{1}{c_1}|I|. \]

  Since \(S(n)=7n-5=\Theta(n)\), there exist constants \(a_1,a_2>0\) such that \(a_1 n\le S(n) \le a_2 n\) for all sufficiently large \(n\), and hence

  \[ \frac{a_1}{c_2}|I| \le S(n) \le \frac{a_2}{c_1}|I|. \]

If all input values use a fixed constant number of bits, then the worst-case running time of the RecursiveSum algorithm (and also of the SumIterative algorithm) is

\[ T(|I|)=\Theta(|I|). \]

Thus, both algorithms are linear in the input size.

• Recursion does not make the algorithm faster: both algorithms read every element once and perform \(n-1\) (recursive) or \(n\) (iterative) additions. The recursive version even executes more steps (\(7n-5\) against \(3n+4\)), because of the overhead of the calls.

17.1.7 Extra memory: the call stack

• Time is not the only resource. Each active call of a recursive function needs its own activation record on the call stack, containing its parameters, its local variables and the return address. In RecursiveSum the parameters and local variables are \(l\), \(r\), \(m\), \(s_1\), \(s_2\): every activation record has constant size.

• A call is active from the moment it starts until it returns. Since the calls are executed depth-first, the active calls at any moment form a path from the root of the call tree to the current node. Therefore:

The maximum number of simultaneously active calls (the recursion depth) equals the height of the call tree plus one. The extra memory used by a recursive algorithm is (at least) proportional to the recursion depth.

Observation 17.3: recursion depth of RecursiveSum

For every \(n\ge 1\), the call tree of RecursiveSum on a sub-array of \(n\) elements has height \(\lceil \log_2 n\rceil\). Hence the recursion depth is \(\lceil \log_2 n\rceil+1\) and the extra memory used by RecursiveSum is \(\Theta(\log_2 n)\).

Proof

Let \(h(n)\) be the height of the call tree. Then \(h(1)=0\) and, for \(n\ge 2\),

\[ h(n)=1+\max\big\{h(\lceil n/2\rceil),\,h(\lfloor n/2\rfloor)\big\}. \]

We prove \(h(n)=\lceil \log_2 n\rceil\) by strong induction. For \(n=1\), \(\lceil \log_2 1\rceil = 0\). Let \(n\ge 2\). Since \(\lceil \log_2 x\rceil\) is non-decreasing in \(x\), by the inductive hypothesis the maximum is attained by the larger half, and \(h(n)=1+\lceil \log_2 \lceil n/2\rceil\rceil\).

Let \(k=\lceil \log_2 n\rceil\ge 1\), i.e., \(2^{k-1}<n\le 2^k\). Dividing by \(2\), we obtain \(2^{k-2}<n/2\le 2^{k-1}\); since \(2^{k-1}\) is an integer, also \(2^{k-2}<\lceil n/2\rceil\le 2^{k-1}\), that is \(\lceil \log_2\lceil n/2\rceil\rceil=k-1\). Therefore \(h(n)=1+(k-1)=k=\lceil \log_2 n\rceil\).

Each activation record has constant size, so the extra memory is \(\Theta(\lceil \log_2 n\rceil+1)=\Theta(\log_2 n)\). □

• In Example 17.2, \(n=7\) and the recursion depth is \(\lceil \log_2 7\rceil+1=3+1=4\): for instance, when RS\((1,1)\) is executed, the active calls are RS\((1,7)\), RS\((1,4)\), RS\((1,2)\) and RS\((1,1)\).

algorithm	number of steps	extra memory
SumIterative	\(3n+4=\Theta(n)\)	\(\Theta(1)\)
RecursiveSum	\(7n-5=\Theta(n)\)	\(\Theta(\log_2 n)\)

17.1.8 A different recursion: decrease by one

• The halving is not the only way to sum an array recursively. The array can also be split in an unbalanced way: the sum of \(a[1..n]\) is the sum of \(a[1..n-1]\) plus \(a[n]\). This is a decrease by one recursion:

Algorithm: RecursiveSumLinear

Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

Output: The sum \(a[1]+a[2]+\cdots+a[n]\)

1function RecursiveSumLinear(a, n)

2if \(n = 1\) then

3return \(a[1]\)// Base case

4end

5\(s :=\) RecursiveSumLinear\((a, n-1)\)

6return \(s + a[n]\)

7end

Run in Colab:PythonC++Java

• Correctness follows by (simple) induction on \(n\): for \(n=1\) the algorithm returns \(a[1]\); for \(n\ge 2\), by the inductive hypothesis \(s=a[1]+\cdots+a[n-1]\), and the algorithm returns \(s+a[n]=a[1]+\cdots+a[n]\).

• If \(n=1\), lines 2 and 3 are executed once: \(S(1)=2\). If \(n\ge 2\), lines 2, 5 and 6 are executed once, plus the \(S(n-1)\) steps of the recursive call:

  \[ S(n)= \begin{cases} 2 & \text{if } n=1,\\ S(n-1)+3 & \text{if } n\ge 2. \end{cases} \]

• The Master Theorem cannot be applied, because the size of the sub-problem is \(n-1\) and not \(n/b\) for a constant \(b>1\). We solve the recurrence by iteration (unrolling):

  \[ S(n) = S(n-1)+3 = S(n-2)+2\cdot 3 = \cdots = S(1)+(n-1)\cdot 3 = 3n-1 = \Theta(n). \]

• The call tree is a path of \(n\) nodes: RecursiveSumLinear\((a,n)\) calls RecursiveSumLinear\((a,n-1)\), which calls RecursiveSumLinear\((a,n-2)\), and so on, until \(n=1\). When the base case is reached, all the \(n\) calls are active.

RecursiveSumLinear executes \(S(n)=3n-1=\Theta(n)\) steps, but its recursion depth is \(n\): it needs \(\Theta(n)\) extra memory for the call stack (against \(\Theta(\log_2 n)\) of RecursiveSum and \(\Theta(1)\) of SumIterative). In practice, for large \(n\) (e.g. \(n=10^7\)) the decrease-by-one version may exhaust the call stack (stack overflow), while RecursiveSum needs only \(\lceil\log_2 10^7\rceil+1=25\) active calls.

Key points on the sum of an array.

• RecursiveSum is correct (strong induction), makes \(2n-1\) calls and executes \(7n-5=\Theta(n)\) steps: recursion does not reduce the work, which is linear because every element must be read.

• The recurrence \(S(n)=2S(n/2)+c\) falls in case 1 of the Master Theorem: the cost is dominated by the \(n\) leaves.

• The call stack costs memory: \(\Theta(\log_2 n)\) for the halving recursion, \(\Theta(n)\) for the decrease-by-one recursion, \(\Theta(1)\) for the loop.

17.2 Merge Sort

For the sum of an array, divide and conquer gave no gain in time. We now meet a problem where it does make a difference: sorting.

17.2.1 The sorting problem

Given an array \(a[1..n]\) of \(n\) natural numbers, we consider the problem of rearranging the elements of the array in non-decreasing order such that:

\[ a[1] \le a[2] \le \cdots \le a[n]. \]

• The problem has been introduced in the chapter «Sorting algorithms», where we studied Insertion Sort, Exchange Sort and Selection Sort. In the chapter «Running time» we proved that the worst-case number of steps of InsertionSort is \(S(n)=\frac{3n^2+9n-8}{2}=\Theta(n^2)\).

• In this section we study Merge Sort, a recursive comparison-based sorting algorithm based on the divide and conquer paradigm, whose number of steps is \(\Theta(n\log_2 n)\) in the worst case.

Example 17.4: a sorting instance

We consider the following array of \(n=7\) natural numbers:

\[ \begin{array}{c|c|c|c|c|c|c|c|} {a[i]} & {i=1} & {i=2} & {i=3} & {i=4} & {i=5} & {i=6} & {i=7} \\ & 9 & 12 & 3 & 16 & 19 & 11 & 12 \end{array} \]

The sorted array is:

\[ \begin{array}{c|c|c|c|c|c|c|c|} {a[i]} & {i=1} & {i=2} & {i=3} & {i=4} & {i=5} & {i=6} & {i=7} \\ & 3 & 9 & 11 & 12 & 12 & 16 & 19 \end{array} \]

17.2.2 The Merge Sort algorithm

Divide and conquer

• Merge Sort sorts a sub-array \(a[l..r]\) as follows:

  1. Divide: split \(a[l..r]\) in two halves \(a[l..m]\) and \(a[m+1..r]\), where \(m=\lfloor (l+r)/2\rfloor\);

  2. Conquer: sort recursively the two halves;

  3. Combine: merge the two sorted halves into a single sorted sub-array \(a[l..r]\).

• The base case is a sub-array with a single element (\(l=r\)), which is already sorted: nothing has to be done.

• The whole work is done in the combine step, by the procedure Merge. The key observation is that two sorted sequences can be merged very efficiently: the smallest element of the result is the smaller of the two first elements, and so on.

Pseudo-code

• This is the pseudo-code of the MergeSort algorithm. To sort the whole array \(a[1..n]\), we call MergeSort\((a,1,n)\).

Algorithm: MergeSort

Input: An array \(a\) and two indices \(l \le r\)

Output: The sub-array \(a[l..r]\) sorted in non-decreasing order

1function MergeSort(a, l, r)

2if \(l < r\) then

3\(m := \lfloor (l+r)/2 \rfloor\)// Divide

4MergeSort\((a, l, m)\)// Conquer (left half)

5MergeSort\((a, m+1, r)\)// Conquer (right half)

6Merge\((a, l, m, r)\)// Combine

7end

8end

Run in Colab:PythonC++Java

• If \(k=r-l+1\ge 2\), the two halves \(a[l..m]\) and \(a[m+1..r]\) have \(\lceil k/2\rceil\) and \(\lfloor k/2\rfloor\) elements, both between \(1\) and \(k-1\): the recursion always reaches the base case.

• The procedure Merge\((a,l,m,r)\) assumes that \(a[l..m]\) and \(a[m+1..r]\) are sorted. It copies them into two auxiliary arrays \(L\) and \(R\), and then it repeatedly moves the smaller of the first two elements not yet copied back into \(a\):

Algorithm: Merge

Input: An array \(a\) and indices \(l\le m<r\) such that \(a[l..m]\) and \(a[m+1..r]\) are sorted

Output: The sub-array \(a[l..r]\) sorted in non-decreasing order

1function Merge(a, l, m, r)

2\(n_1 := m-l+1\)

3\(n_2 := r-m\)

4\(L :=\) new array\([1..n_1]\), \(R :=\) new array\([1..n_2]\)

5for \(i := 1\) to \(n_1\) do

6\(L[i] := a[l+i-1]\)

7end

8for \(j := 1\) to \(n_2\) do

9\(R[j] := a[m+j]\)

10end

11\(i := 1\)

12\(j := 1\)

13\(k := l\)

14while \(i \le n_1\) and \(j \le n_2\) do

15if \(L[i] \le R[j]\) then

16\(a[k] \leftarrow L[i]\)

17\(i \leftarrow i+1\)

18else

19\(a[k] \leftarrow R[j]\)

20\(j \leftarrow j+1\)

21end

22\(k \leftarrow k+1\)

23end

24while ( do

25end

26[f]Copy the rest of \(L\))\(i \le n_1\) \(a[k] \leftarrow L[i]\) \(i \leftarrow i+1\) \(k \leftarrow k+1\)

27while ( do

28end

29[f]Copy the rest of \(R\))\(j \le n_2\) \(a[k] \leftarrow R[j]\) \(j \leftarrow j+1\) \(k \leftarrow k+1\)

30end

Run in Colab:PythonC++Java

• Explanation of Merge:

  • Lines 2–9 copy \(a[l..m]\) into \(L[1..n_1]\) and \(a[m+1..r]\) into \(R[1..n_2]\). The copies are necessary, because the positions \(a[l..r]\) are overwritten during the merge.

  • The indices \(i\) and \(j\) point to the first elements of \(L\) and \(R\) not yet copied back, and \(k\) points to the next position of \(a\) to be filled.

  • The first while loop (line 14) compares \(L[i]\) and \(R[j]\) and copies the smaller one into \(a[k]\) (in case of a tie, the element of \(L\) is copied first: this makes Merge Sort stable).

  • As soon as one of the two arrays is exhausted, the remaining elements of the other one (which are already sorted, and not smaller than the ones already copied) are copied into \(a\) by the while loop of line 26 or by the one of line 29. Only one of these two loops executes at least one iteration.

Examples

We now run Merge Sort on the array of Example 17.4: first we look at the whole call tree, then at the two phases of the algorithm, and finally at a single call of Merge.

Example 17.5: call tree of MergeSort

We consider the array of Example 17.4, i.e., \(a=[9,12,3,16,19,11,12]\). This is the call tree of MergeSort\((a,1,7)\), where each node MS\((l,r)\) is a call on the sub-array \(a[l..r]\). In each node, in blue the sub-array received by the call and in red the sorted sub-array produced by the call (after its Merge):

The calls of Merge are executed in the following order (depth-first), and this is the content of the array after each of them (the sub-array modified by each call is in red):

call	merged sub-arrays	array \(a\) after the call
Merge\((a,1,1,2)\)	\([9]\) and \([12]\)	\([\red{9,12},3,16,19,11,12]\)
Merge\((a,3,3,4)\)	\([3]\) and \([16]\)	\([9,12,\red{3,16},19,11,12]\)
Merge\((a,1,2,4)\)	\([9,12]\) and \([3,16]\)	\([\red{3,9,12,16},19,11,12]\)
Merge\((a,5,5,6)\)	\([19]\) and \([11]\)	\([3,9,12,16,\red{11,19},12]\)
Merge\((a,5,6,7)\)	\([11,19]\) and \([12]\)	\([3,9,12,16,\red{11,12,19}]\)
Merge\((a,1,4,7)\)	\([3,9,12,16]\) and \([11,12,19]\)	\([\red{3,9,11,12,12,16,19}]\)

Example 17.6: divide and combine phases of MergeSort

We consider again the array of Example 17.4. The upper part of the figure shows the divide phase (violet arrows): each sub-array is split into its left half (in red) and its right half (in blue), until sub-arrays of one element are obtained. The lower part shows the combine phase (orange arrows): pairs of sorted sub-arrays are merged into a sorted sub-array.

Example 17.7: trace of Merge

We consider the last call Merge\((a,1,4,7)\) of Example 17.5. Before the call \(a=[3,9,12,16,11,12,19]\), with \(a[1..4]\) and \(a[5..7]\) sorted. Then \(n_1=4\), \(n_2=3\) and

\[ L=[3,9,12,16], \qquad R=[11,12,19]. \]

This is the execution of the while loops (one row per element copied into \(a\)):

\(k\)	\(i\)	\(j\)	\(L[i]\)	\(R[j]\)	comparison	action
1	1	1	3	11	\(3 \le 11\)	\(a[1]\leftarrow 3\), \(i=2\)
2	2	1	9	11	\(9 \le 11\)	\(a[2]\leftarrow 9\), \(i=3\)
3	3	1	12	11	\(12 > 11\)	\(a[3]\leftarrow 11\), \(j=2\)
4	3	2	12	12	\(12 \le 12\)	\(a[4]\leftarrow 12\) (from \(L\)), \(i=4\)
5	4	2	16	12	\(16 > 12\)	\(a[5]\leftarrow 12\) (from \(R\)), \(j=3\)
6	4	3	16	19	\(16 \le 19\)	\(a[6]\leftarrow 16\), \(i=5\)
7	5	3	–	19	\(L\) exhausted	\(a[7]\leftarrow 19\), \(j=4\)

After \(6\) iterations of the first while loop (and \(6\) comparisons), \(i=5>n_1\): the array \(L\) is exhausted, and the last element of \(R\) is copied by the while loop of line 29. The result is \(a=[3,9,11,12,12,16,19]\).

17.2.3 Correctness

The correctness of Merge Sort rests on two facts: Merge correctly merges two sorted sub-arrays (a property of a loop, proved with a loop invariant), and the recursion is correct (proved by strong induction, as for RecursiveSum).

Correctness of Merge

• We prove the correctness of Merge by a loop invariant, i.e., a property that holds at the beginning of every iteration of a loop. As in the chapter «Correctness», we show that the invariant holds before the first iteration (initialization), that if it holds before an iteration it also holds before the next one (maintenance), and what it gives us when the loop ends (termination).

Observation 17.4: loop invariant of Merge

Let \(a[l..m]\) and \(a[m+1..r]\) be sorted. At the beginning of every iteration of the while loop of line 14 of Merge:

• (I1) the sub-array \(a[l..k-1]\) contains the \(k-l\) elements of \(L[1..i-1]\) and \(R[1..j-1]\), in non-decreasing order;

• (I2) every element of \(a[l..k-1]\) is smaller than or equal to every element of \(L[i..n_1]\) and of \(R[j..n_2]\).

At the end, Merge terminates and \(a[l..r]\) contains the elements originally in \(a[l..r]\), sorted in non-decreasing order.

Proof

After lines 2–9, \(L[1..n_1]\) and \(R[1..n_2]\) are copies of the sorted sub-arrays \(a[l..m]\) and \(a[m+1..r]\), hence they are sorted.

Initialization. Before the first iteration \(k=l\), \(i=1\), \(j=1\): the sub-array \(a[l..k-1]\) is empty, and (I1) and (I2) hold trivially.

Maintenance. Assume (I1) and (I2) at the beginning of an iteration, and suppose \(L[i]\le R[j]\) (the other case is symmetric). Since \(L\) and \(R\) are sorted, \(L[i]\le L[i+1..n_1]\) and \(L[i]\le R[j]\le R[j+1..n_2]\): \(L[i]\) is the smallest element not yet copied. By (I2), \(L[i]\) is greater than or equal to all the elements of \(a[l..k-1]\), so after \(a[k]\leftarrow L[i]\) the sub-array \(a[l..k]\) is sorted and contains \(L[1..i]\) and \(R[1..j-1]\). After \(i\leftarrow i+1\) and \(k\leftarrow k+1\), (I1) holds again. (I2) holds as well, because the elements not yet copied are a subset of the previous ones, and the new element \(a[k-1]=L[i-1]\) is smaller than or equal to all of them.

Termination. Every iteration increases \(i+j\) by one, so the loop ends after at most \(n_1+n_2\) iterations, with \(i=n_1+1\) or \(j=n_2+1\). Suppose \(i=n_1+1\) (the other case is symmetric). The loop of line 26 is skipped, and the loop of line 29 copies \(R[j..n_2]\), in this order, into \(a[k..r]\). Since \(R[j..n_2]\) is sorted and, by (I2), its elements are not smaller than those of \(a[l..k-1]\), the whole sub-array \(a[l..r]\) is sorted. By (I1), it contains exactly the elements of \(L\) and \(R\), i.e., the elements originally in \(a[l..r]\). □

Correctness of MergeSort

Observation 17.5: correctness of MergeSort

For every pair of indices \(l\le r\), the call MergeSort\((a,l,r)\) terminates and rearranges the elements of \(a[l..r]\) in non-decreasing order (without modifying the rest of the array).

Proof

We use strong induction on the number \(k=r-l+1\ge 1\) of elements of the sub-array.

Base case (\(k=1\)). Then \(l=r\), the condition of line 2 is false and nothing is done: a sub-array of one element is sorted.

Inductive step (\(k\ge 2\)). Assume that the statement holds for all sub-arrays with fewer than \(k\) elements. Since \(l<r\), the algorithm computes \(m=\lfloor (l+r)/2\rfloor\), with \(l\le m<r\). The sub-arrays \(a[l..m]\) and \(a[m+1..r]\) have \(\lceil k/2\rceil\) and \(\lfloor k/2\rfloor\) elements, both between \(1\) and \(k-1\). By the inductive hypothesis, after lines 4 and 5 both \(a[l..m]\) and \(a[m+1..r]\) are sorted (and contain the same elements as before). Therefore the hypothesis of Merge is satisfied, and by Observation 17.4, after line 6 the sub-array \(a[l..r]\) is sorted. □

17.2.4 Number of steps

Number of steps of Merge

• Let \(n=r-l+1=n_1+n_2\) be the number of elements to be merged, and let \(t\) be the number of iterations of the while loop of line 14. Among them, \(t_L\) copy an element of \(L\) and \(t_R\) copy an element of \(R\), with \(t_L+t_R=t\). The header of a for loop from \(1\) to \(n_1\) is executed \(n_1+1\) times (the last test fails). The line else is part of the if of line 15 and is not counted separately.

  The number of times each line of code is executed is:

  • Lines 2, 3, 4 are executed \(1\) time each

  • Line 5 is executed \(n_1+1\) times and line 6 \(n_1\) times

  • Line 8 is executed \(n_2+1\) times and line 9 \(n_2\) times

  • Lines 11, 12, 13 are executed \(1\) time each

  • Line 14 is executed \(t+1\) times

  • Line 15 is executed \(t\) times

  • Lines 16, 17 are executed \(t_L\) times each

  • Lines 19, 20 are executed \(t_R\) times each

  • Line 22 is executed \(t\) times

  • Line 26 is executed \((n_1-t_L)+1\) times and lines 26, 26, 26 \(n_1-t_L\) times each

  • Line 29 is executed \((n_2-t_R)+1\) times and lines 29, 29, 29 \(n_2-t_R\) times each

  Therefore, the total number of steps of Merge is

  \[\begin{align*} & 3 + (2n_1+1) + (2n_2+1) + 3 + (t+1) + t + 2t_L + 2t_R + t + 4(n_1-t_L)+1 + 4(n_2-t_R)+1 \\[1ex] &= 11 + 2n + 5t + 4(n-t) = 6n + t + 11. \end{align*}\]

• Every iteration of the first while loop copies one element into \(a\), so \(t\le n\). More precisely:

  • the loop stops as soon as one of the two arrays is exhausted, so \(t\ge \min\{n_1,n_2\}\);

  • when the loop stops, the other array still contains at least one element, so \(t\le n-1\).

  Hence the number of steps of Merge on \(n\) elements is between \(6n+11+\min\{n_1,n_2\}\) and \(7n+10\); in particular, it is between \(6n+11\) and \(7n+10\). The worst case \(t=n-1\) happens, for instance, in Example 17.7 (\(n=7\), \(t=6\), \(6\cdot 7+6+11=59\) steps).

The number of steps of Merge on \(n=r-l+1\) elements is \(6n+t+11\) and satisfies

\[ 6n+11 \;\le\; S_{\texttt{Merge}}(n) \;\le\; 7n+10, \qquad\text{hence}\qquad S_{\texttt{Merge}}(n)=\Theta(n). \]

The number of comparisons between elements (line 15) is \(t\), with \(\min\{n_1,n_2\}\le t\le n-1\).

The recurrence of MergeSort

• Let \(S(n)\) denote the number of steps executed by MergeSort in the worst case on a sub-array of \(n=r-l+1\) elements. As for the sum of an array, a line containing a call counts \(1\) step plus the steps of the called function.

• If \(n=1\), only line 2 is executed: \(S(1)=1\).

• If \(n\ge 2\):

  • Line 2 is executed \(1\) time

  • Line 3 is executed \(1\) time

  • Line 4 is executed \(1\) time, plus the \(S(\lceil n/2\rceil)\) steps of the call

  • Line 5 is executed \(1\) time, plus the \(S(\lfloor n/2\rfloor)\) steps of the call

  • Line 6 is executed \(1\) time, plus the \(S_{\texttt{Merge}}(n)\) steps of Merge

  and therefore

  \[ S(n)=S(\lceil n/2\rceil)+S(\lfloor n/2\rfloor)+f(n), \qquad f(n)=5+S_{\texttt{Merge}}(n). \]

• From the analysis of Merge, \(6n+16\le f(n)\le 7n+15\). Since \(7n+15\le 15n\) for \(n\ge 2\), we have

  \[ 6n \le f(n) \le 15\,n \qquad \text{for every } n\ge 2, \qquad\text{i.e.,}\qquad f(n)=\Theta(n). \]

The number of steps of MergeSort is described by the recurrence

\[ S(n)= \begin{cases} 1 & \text{if } n=1,\\[1mm] S\big(\lceil n/2\rceil\big)+S\big(\lfloor n/2\rfloor\big)+\Theta(n) & \text{if } n\ge 2, \end{cases} \]

which, ignoring floors and ceilings, we write as

\[ S(n)=2\,S(n/2)+\Theta(n). \]

Solution with the recursion tree

• Assume that \(n=2^h\) is an exact power of \(2\), and let \(c=15\) be the constant such that \(f(n)\le c\,n\) (with \(S(1)=1\le c\)). We first bound \(S(n)\) from above by the recursion tree of

  \[ S(n)\le 2\,S(n/2)+c\,n, \]

  where each node contains the cost of a call, excluding the cost of its recursive calls:

• The top level has cost \(c\,n\); the next level has cost \(c\frac{n}{2}+c\frac{n}{2}=c\,n\); the level after has cost \(4\cdot c\frac{n}{4}=c\,n\), and so on. In general, level \(i\) has \(2^i\) nodes, each corresponding to a sub-array of \(n/2^i\) elements and contributing a cost of at most \(c\,n/2^i\), so each level costs at most

  \[ 2^i\cdot c\,\frac{n}{2^i} = c\,n. \]

• The bottom level \(\log_2 n\) has \(n\) leaves (sub-arrays of one element), each with cost \(S(1)=1\le c\): its cost is at most \(c\,n\).

• The levels are \(0,1,\dots,\log_2 n\), i.e., \(\log_2 n+1\). Summing the costs of all the levels:

  \[ S(n)\le c\,n\,(\log_2 n+1) = c\,n\log_2 n + c\,n . \]

• In the same way, using \(f(n)\ge 6n\), each internal level costs at least \(6n\), and there are \(\log_2 n\) internal levels: \(S(n)\ge 6\,n\log_2 n\).

• Therefore, for \(n\) a power of \(2\),

  \[ 6\,n\log_2 n \;\le\; S(n) \;\le\; 15\,n\log_2 n+15\,n, \qquad\text{i.e.,}\qquad S(n)=\Theta(n\log_2 n), \]

  since

  \[ \lim_{n\to\infty}\frac{15\,n\log_2 n+15\,n}{n\log_2 n}=\lim_{n\to\infty}\left(15+\frac{15}{\log_2 n}\right)=15\in\R_{>0}. \]

• Contrary to the recursion tree of the sum of an array, where the cost of the levels doubles at each level, here all the levels have the same cost \(c\,n\): the total is the cost of one level times the number of levels. This is exactly the situation of case 2 of the Master Theorem.

Solution with the Master Theorem

• We recall case 2 of the Master Theorem:

Let \(S(n)=a\,S(n/b)+f(n)\), with \(a\ge 1\) and \(b>1\) constants and \(f(n)\) asymptotically positive. If \(f(n)=\Theta\big(n^{\log_b a}\log^k n\big)\) for some constant \(k\ge 0\), then

\[ S(n)=\Theta\big(n^{\log_b a}\log^{k+1} n\big). \]

• \(S(n)=2\,S(n/2)+\Theta(n)\) \(\quad\rightarrow\quad\) \(a=2\), \(b=2\), \(f(n)=\Theta(n)\).

• \(n^{\log_b a}=n^{\log_2 2}=n\).

• Comparison: \(f(n)\) and \(n^{\log_b a}\) grow in the same way \(\quad\rightarrow\quad\) case 2.

• Hypothesis: \(f(n)=\Theta(n)=\Theta\big(n^{\log_2 2}\log^0 n\big)\) with \(k=0\).

• Conclusion: \(S(n)=\Theta\big(n^{\log_2 2}\log^{1} n\big)=\Theta(n\log n)\).

The base of the logarithm is irrelevant inside \(\Theta\), because \(\log_b n=\frac{\log_2 n}{\log_2 b}\) differs from \(\log_2 n\) by a constant factor. Hence \(S(n)=\Theta(n\log_2 n)\), in agreement with the recursion tree.

Worst-case running time

• We make the hypothesis that every entry of the array is stored using a fixed constant number of bits. Then \(|I|=\Theta(n)\): there exist constants \(c_1,c_2>0\) such that, for all sufficiently large \(n\),

  \[ \frac{1}{c_2}|I| \le n \le \frac{1}{c_1}|I|. \]

  Taking logarithms, \(\log_2|I|-\log_2 c_2\le \log_2 n\le \log_2|I|-\log_2 c_1\), hence, for sufficiently large \(|I|\),

  \[ \frac{1}{2}\log_2|I| \le \log_2 n \le 2\log_2|I|. \]

  Multiplying the two chains of inequalities (all terms are positive),

  \[ \frac{1}{2c_2}\,|I|\log_2|I| \;\le\; n\log_2 n \;\le\; \frac{2}{c_1}\,|I|\log_2|I|, \]

  that is, \(n\log_2 n=\Theta(|I|\log_2|I|)\). Since \(S(n)=\Theta(n\log_2 n)\), we obtain \(S(n)=\Theta(|I|\log_2|I|)\).

If all input values use a fixed constant number of bits, then the worst-case running time of the MergeSort algorithm is

\[ T(|I|)=\Theta(|I|\log |I|). \]

17.2.5 Extra memory

• Merge\((a,l,m,r)\) allocates the auxiliary arrays \(L\) and \(R\), with \(n_1+n_2=r-l+1\) elements in total, which are released when Merge returns.

• Merge is called only after both recursive calls have returned, so at any moment at most one Merge is active, and the largest auxiliary arrays are the ones of the first call MergeSort\((a,1,n)\), with \(n\) elements in total.

• In addition, the call stack contains at most \(\lceil\log_2 n\rceil+1\) activation records of constant size (the call tree has the same shape as the one of RecursiveSum, Observation 17.3): \(\Theta(\log_2 n)\) memory.

MergeSort uses \(\Theta(n)+\Theta(\log_2 n)=\Theta(n)\) extra memory: it is not an in-place sorting algorithm. On the contrary, InsertionSort sorts in place, with \(\Theta(1)\) extra memory.

17.2.6 Comparison with Insertion Sort

• In the worst case, InsertionSort executes \(\Theta(n^2)\) steps, while MergeSort executes \(\Theta(n\log_2 n)\) steps. Since

  \[ \lim_{n\to\infty}\frac{n\log_2 n}{n^2}=\lim_{n\to\infty}\frac{\log_2 n}{n}=0, \]

  Merge Sort is asymptotically much faster.

• To get a feeling of the difference, we ignore the multiplicative constants and assume that a computer executes \(10^9\) steps per second:

\(n\)	\(n^2\)	\(n\log_2 n\)	time for \(n^2\) steps	time for \(n\log_2 n\) steps
\(10\)	\(100\)	\(\approx 33\)	\(10^{-7}\) s	\(\approx 3.3\cdot 10^{-8}\) s
\(10^3\)	\(10^6\)	\(\approx 9\,966\)	\(10^{-3}\) s	\(\approx 10^{-5}\) s
\(10^6\)	\(10^{12}\)	\(\approx 1.99\cdot 10^{7}\)	\(10^{3}\) s \(\approx 16.7\) min	\(\approx 0.02\) s

• For small arrays the difference is negligible (and, because of the constants and of the cost of the recursive calls, InsertionSort can even be faster). For large arrays, Merge Sort is dramatically faster: with \(n=10^6\) elements it is about \(50\,000\) times faster.

Key points on Merge Sort.

• All the work is done by Merge, which merges two sorted sub-arrays of total size \(n\) in \(6n+t+11=\Theta(n)\) steps.

• The recurrence \(S(n)=2S(n/2)+\Theta(n)\) falls in case 2 of the Master Theorem: \(\log_2 n+1\) levels of cost \(\Theta(n)\) each, \(S(n)=\Theta(n\log_2 n)\).

• The price is memory: \(\Theta(n)\) for the auxiliary arrays.

algorithm	worst-case number of steps	extra memory
InsertionSort	\(\Theta(n^2)\)	\(\Theta(1)\)
MergeSort	\(\Theta(n\log_2 n)\)	\(\Theta(n)\)

17.3 Recursive Binary Search

Merge Sort makes two recursive calls on the two halves. The next algorithm makes only one: after a single comparison, one of the two halves can be discarded.

17.3.1 The algorithm

Given an array \(a[1..n]\) of \(n\) natural numbers sorted in non-decreasing order and a target natural number \(m\), we consider the problem of determining if \(m\) is one of the elements of the array.

• In the chapter «Linear and binary search» we solved this problem with the iterative algorithm BinarySearch: the algorithm maintains a search interval \(a[left..right]\), initially \(a[1..n]\), and at each iteration it compares the target \(m\) with the middle element

  \[ a[mid], \qquad mid = left + \left\lfloor \frac{right-left}{2} \right\rfloor . \]

  If \(a[mid]=m\) the element is found; otherwise, since the array is sorted, half of the interval can be discarded.

• The key observation is that, after the comparison with \(a[mid]\), the problem that remains to be solved is the same problem (search \(m\) in a sorted array) on a smaller sub-array:

  • if \(a[mid] < m\), then \(m\) can only be in \(a[mid+1..right]\);

  • if \(a[mid] > m\), then \(m\) can only be in \(a[left..mid-1]\).

• This is exactly the structure required by a recursive algorithm: we solve the problem on \(a[left..right]\) by solving the same problem on a sub-array of (about) half the size. The base cases are the empty interval (\(left > right\)), in which \(m\) is certainly not present, and the case \(a[mid]=m\), in which \(m\) is found.

• Differently from the iterative version, the boundaries \(left\) and \(right\) are now parameters of the function. To search \(m\) in the whole array, we call

  \[ \texttt{RecursiveBinarySearch}(a,1,n,m). \]

• This is the pseudo-code of the Recursive Binary Search algorithm:

Algorithm: RecursiveBinarySearch

Input: An array \(a[1..n]\) of \(n\) natural numbers sorted in non-decreasing order, two indices \(left\) and \(right\), and a target value \(m\)

Output: An index \(i \in \{left,\dots,right\}\) such that \(a[i]=m\), or \(-1\) if \(m\) is not in \(a[left..right]\)

1function RecursiveBinarySearch(a, left, right, m)

2if \(left > right\) then

3return \(-1\)// Empty interval: not found

4end

5\(mid := left + \lfloor (right - left) / 2 \rfloor\)// Middle index

6if \(a[mid] = m\) then

7return \(mid\)// Element found

8end

9if \(a[mid] < m\) then

10return RecursiveBinarySearch(\(a\), \(mid+1\), \(right\), \(m\))

11end

12return RecursiveBinarySearch(\(a\), \(left\), \(mid-1\), \(m\))

13end

Run in Colab:PythonC++Java

• Explanation of the algorithm:

  • Lines 2–3: if the interval is empty (\(left > right\)), the element is not present and \(-1\) is returned (base case).

  • Line 5: the middle index \(mid\) is computed with the same formula as in the iterative algorithm.

  • Lines 6–7: if \(a[mid] = m\), the element is found and its index is returned (base case).

  • Lines 9–10: if \(a[mid] < m\), the search continues recursively in the right half \(a[mid+1..right]\).

  • Line 12: otherwise \(a[mid] > m\), and the search continues recursively in the left half \(a[left..mid-1]\).

  • The value returned by the recursive call is returned unchanged to the caller.

• Each call of RecursiveBinarySearch performs at most one recursive call. Therefore, the call tree is a path: it has no branching. This is very different from Merge Sort, where every call on an array with at least two elements generates two recursive calls.

17.3.2 Examples

• We consider the same searches performed in the chapter «Linear and binary search» with the iterative algorithm. For each search we report one row for each call: the values of \(left\), \(right\), \(mid\), \(a[mid]\) and the action executed. Then, we draw the call tree: a black arrow is a recursive call, a blue arrow is the value returned to the caller.

Example 17.9: Recursive Binary Search on a sorted array

We search four values in the sorted array \(a = [3, 9, 11, 12, 12, 16, 19]\) (\(n=7\)).

• Search for \(m = 12\). First call RecursiveBinarySearch\((a,1,7,12)\):

  call	\(left\)	\(right\)	\(mid\)	\(a[mid]\)	action
  \(1\)	1	7	4	12	\(a[mid] = m\) \(\Rightarrow\) Found! Return \(4\)

  

  Element 12 is found at index 4 with a single call (no recursion).

• Search for \(m = 10\). First call RecursiveBinarySearch\((a,1,7,10)\):

  call	\(left\)	\(right\)	\(mid\)	\(a[mid]\)	action
  \(1\)	1	7	4	12	\(a[mid] > m\) \(\Rightarrow\) call on \(left=1\), \(right = 3\)
  \(2\)	1	3	2	9	\(a[mid] < m\) \(\Rightarrow\) call on \(left=3\), \(right = 3\)
  \(3\)	3	3	3	11	\(a[mid] > m\) \(\Rightarrow\) call on \(left=3\), \(right = 2\)
  \(4\)	3	2	–	–	\(left > right\) \(\Rightarrow\) Not found! Return \(-1\)

  

  Element 10 is not in the array: the last call is on an empty interval and returns \(-1\), and this value is propagated back to the first call.

• Search for \(m = 3\). First call RecursiveBinarySearch\((a,1,7,3)\):

  call	\(left\)	\(right\)	\(mid\)	\(a[mid]\)	action
  \(1\)	1	7	4	12	\(a[mid] > m\) \(\Rightarrow\) call on \(left=1\), \(right = 3\)
  \(2\)	1	3	2	9	\(a[mid] > m\) \(\Rightarrow\) call on \(left=1\), \(right = 1\)
  \(3\)	1	1	1	3	\(a[mid] = m\) \(\Rightarrow\) Found! Return \(1\)

  

  Element 3 is found at index 1.

• Search for \(m = 19\). First call RecursiveBinarySearch\((a,1,7,19)\):

  call	\(left\)	\(right\)	\(mid\)	\(a[mid]\)	action
  \(1\)	1	7	4	12	\(a[mid] < m\) \(\Rightarrow\) call on \(left=5\), \(right = 7\)
  \(2\)	5	7	6	16	\(a[mid] < m\) \(\Rightarrow\) call on \(left=7\), \(right = 7\)
  \(3\)	7	7	7	19	\(a[mid] = m\) \(\Rightarrow\) Found! Return \(7\)

  

  Element 19 is found at index 7.

• The sequence of values \((left, right, mid)\) is exactly the same as the sequence produced by the iterative algorithm: each call of the recursive algorithm corresponds to one iteration of the while loop of the iterative algorithm.

• Note that the second occurrence of \(12\) (index 5) is never found when searching \(m=12\): as in the iterative version, the algorithm returns one index \(i\) with \(a[i]=m\), not necessarily the first one.

17.3.3 Correctness

• As for the previous algorithms, the correctness is proved by strong induction on the size of the input of the call. The size of the call RecursiveBinarySearch\((a,left,right,m)\) is the number of elements of the interval:

  \[ k = right - left + 1 . \]

  For an empty interval (\(left = right+1\)) we have \(k=0\).

Theorem 17.6: correctness of Recursive Binary Search

Let \(a[1..n]\) be sorted in non-decreasing order and let \(1 \le left \le right+1 \le n+1\). Then RecursiveBinarySearch\((a,left,right,m)\) terminates and returns:

• an index \(i \in \{left,\dots,right\}\) such that \(a[i]=m\), if \(m\) is one of the elements of \(a[left..right]\);

• \(-1\), otherwise.

Proof

We proceed by strong induction on \(k = right-left+1 \ge 0\).

Base case \(k=0\). Then \(left > right\), the interval is empty and \(m\) is not one of its elements. The algorithm executes lines 2–3 and returns \(-1\), which is correct.

Inductive step. Let \(k \ge 1\) and assume (inductive hypothesis) that the statement holds for every call whose interval has size \(k' < k\). Since \(left \le right\), the algorithm computes

\[ mid = left + \left\lfloor \frac{right-left}{2} \right\rfloor, \qquad left \le mid \le right . \]

• If \(a[mid]=m\), the algorithm returns \(mid \in \{left,\dots,right\}\), which is correct.

• If \(a[mid] < m\), then, since the array is sorted, \(a[i] \le a[mid] < m\) for every \(i \in \{left,\dots,mid\}\). Hence \(m\) is in \(a[left..right]\) if and only if it is in \(a[mid+1..right]\). This interval has size \(right-mid < k\) (because \(mid \ge left\)), so by the inductive hypothesis the call RecursiveBinarySearch\((a,mid+1,right,m)\) terminates and returns a correct answer, which is returned unchanged.

• If \(a[mid] > m\), then \(a[i] \ge a[mid] > m\) for every \(i \in \{mid,\dots,right\}\). Hence \(m\) is in \(a[left..right]\) if and only if it is in \(a[left..mid-1]\), an interval of size \(mid-left < k\) (because \(mid \le right\)). By the inductive hypothesis, the recursive call returns a correct answer.

In all cases the call terminates and returns a correct answer. □

• Applying Theorem 17.6 with \(left=1\) and \(right=n\), we obtain that RecursiveBinarySearch\((a,1,n,m)\) solves the problem.

17.3.4 Worst-case running time

The recurrence

• Let \(S(n)\) denote the number of steps executed by RecursiveBinarySearch in the worst case on an interval of \(n = right-left+1\) elements (including the steps executed by all the recursive calls).

• The number of steps executed by a single call, without counting the steps of the recursive call, is:

  • empty interval: lines 2 and 3 \(\Rightarrow\) \(2\) steps;

  • element found: lines 2, 5, 6, 7 \(\Rightarrow\) \(4\) steps;

  • recursive call: lines 2, 5, 6, 9 and line 10 (or 12) \(\Rightarrow\) \(5\) steps.

• Size of the sub-problems. Let \(n = right-left+1 \ge 1\). Since \(mid - left = \lfloor (n-1)/2 \rfloor\):

  • the left interval \(a[left..mid-1]\) has \(mid-left = \left\lfloor \frac{n-1}{2}\right\rfloor\) elements;

  • the right interval \(a[mid+1..right]\) has \(right-mid = (n-1) - \left\lfloor \frac{n-1}{2}\right\rfloor = \left\lceil \frac{n-1}{2}\right\rceil = \left\lfloor \frac{n}{2}\right\rfloor\) elements.

  For example, for \(n=7\) both halves have \(3\) elements; for \(n=8\) the left half has \(3\) elements and the right half has \(4\).

• In the worst case the element is not found before the interval becomes empty, and the recursion continues on the larger half, which has \(\lfloor n/2 \rfloor\) elements (one can easily check by induction that \(S\) is non-decreasing). Therefore, \(S(n)\) satisfies the recurrence

  \[ S(n) = \begin{cases} 2 & \text{if } n = 0,\\[2mm] S\big(\lfloor n/2 \rfloor\big) + 5 & \text{if } n \ge 1. \end{cases} \]

  This worst case happens, for example, when \(m > a[n]\): the algorithm always continues in the right half, until the interval becomes empty.

• In general, we write

  \[ S(n) = S\big(\lfloor n/2 \rfloor\big) + c , \]

  where \(c\) is a constant (here \(c=5\)): a recursive algorithm that reduces the problem to one sub-problem of half the size, doing a constant amount of extra work.

Solution by expansion

• We expand the recurrence, using the property \(\big\lfloor \lfloor n/2^i \rfloor / 2 \big\rfloor = \lfloor n/2^{i+1} \rfloor\):

  \[ \begin{aligned} S(n) &= S\big(\lfloor n/2 \rfloor\big) + 5 \\ &= S\big(\lfloor n/4 \rfloor\big) + 5 + 5 \\ &= S\big(\lfloor n/8 \rfloor\big) + 5\cdot 3 \\ &\;\;\vdots \\ &= S\big(\lfloor n/2^j \rfloor\big) + 5\, j . \end{aligned} \]

• The expansion stops at the first \(j\) such that \(\lfloor n/2^j \rfloor = 0\), that is \(2^j > n\). For \(n\ge 1\), this is

  \[ j = \lfloor \log_2 n \rfloor + 1 , \]

  because \(2^{\lfloor \log_2 n\rfloor} \le n < 2^{\lfloor \log_2 n \rfloor +1}\). Hence, for every \(n \ge 1\),

  \[ S(n) = 5\big(\lfloor \log_2 n \rfloor + 1\big) + 2 . \]

• For example, \(S(7) = 5\cdot(2+1)+2 = 17\): in the search for \(m=10\) in Example 17.9, the three calls on non-empty intervals execute \(5\) steps each and the last call (empty interval) executes \(2\) steps.

• Since \(\log_2 n - 1 < \lfloor \log_2 n \rfloor \le \log_2 n\), we have

  \[ \lim_{n\to\infty}\frac{S(n)}{\log_2 n} = \lim_{n\to\infty}\frac{5\lfloor \log_2 n \rfloor + 7}{\log_2 n} = 5 \in \R_{>0}, \qquad\text{therefore}\qquad S(n) = \Theta(\log_2 n). \]

Solution by the Master Theorem

• The same result is obtained immediately with the Master Theorem, applied to

  \[ S(n) = S(n/2) + c \]

  (as usual, floors do not change the asymptotic solution).

  • Identify \(a\), \(b\), \(f(n)\): \(a = 1\), \(b = 2\), \(f(n) = c\).

  • Compute \(n^{\log_b a} = n^{\log_2 1} = n^0 = 1\).

  • Compare: \(f(n) = c = \Theta(1) = \Theta\big(n^{\log_2 1}\log^0 n\big)\).

  • Verify the hypothesis: we are in case 2 of the Master Theorem with \(k = 0\).

  • Conclude:

    \[ S(n) = \Theta\big(n^{\log_2 1}\log^{0+1} n\big) = \Theta(\log n) = \Theta(\log_2 n). \]

Number of recursive calls

• Each call on a non-empty interval compares \(m\) with exactly one element \(a[mid]\). Therefore, the number of calls on a non-empty interval is the number of elements of the array examined by the algorithm (exactly as the number of iterations of the while loop of the iterative algorithm).

Observation 17.7: number of calls of Recursive Binary Search

For \(n \ge 1\), the call RecursiveBinarySearch\((a,1,n,m)\) executes at most

\[ \lfloor \log_2 n \rfloor + 1 \]

calls on a non-empty interval, and this bound is attained (for example when \(m > a[n]\)). Counting also the final call on an empty interval, the total number of calls is at most \(\lfloor \log_2 n \rfloor + 2\).

Proof

Let \(n_i\) be the size of the interval of the \(i\)-th call (\(i=1\) is the first call, so \(n_1 = n\)). By the analysis of the sub-problems, \(n_{i+1} \le \lfloor n_i/2 \rfloor\). By induction on \(i\),

\[ n_i \le \left\lfloor \frac{n}{2^{i-1}} \right\rfloor : \]

it holds for \(i=1\), and if it holds for \(i\) then \(n_{i+1} \le \lfloor n_i/2\rfloor \le \big\lfloor \lfloor n/2^{i-1}\rfloor/2\big\rfloor = \lfloor n/2^{i}\rfloor\).

If the \(i\)-th call is on a non-empty interval, then \(n_i \ge 1\), hence \(n/2^{i-1} \ge 1\), i.e., \(2^{i-1} \le n\) and \(i-1 \le \log_2 n\). Since \(i-1\) is an integer, \(i-1 \le \lfloor \log_2 n \rfloor\), i.e.,

\[ i \le \lfloor \log_2 n \rfloor + 1 . \]

Thus, at most \(\lfloor \log_2 n \rfloor + 1\) calls are on a non-empty interval, and at most one further call (on an empty interval, which makes no recursive call) can follow.

If \(m > a[n]\), the algorithm always continues in the right half, whose size is exactly \(\lfloor n_i/2 \rfloor\). Hence \(n_i = \lfloor n/2^{i-1} \rfloor\), which is \(\ge 1\) for \(i = \lfloor \log_2 n\rfloor + 1\): the bound is attained, and it is followed by one call on an empty interval. □

• For example, for \(n = 7\) we have \(\lfloor \log_2 7 \rfloor + 1 = 3\): in the search of \(m = 10\) there are \(3\) calls on non-empty intervals, plus the final call on the empty interval \(left=3\), \(right=2\).

• The same reasoning shows that also the iterative algorithm executes at most \(\lfloor \log_2 n \rfloor + 1\) iterations of the while loop.

Worst-case running time as a function of the input size

• The input of the algorithm consists of the array \(a[1..n]\) and of the target \(m\). Under the hypothesis that every value uses a constant number of bits, the input size satisfies

  \[ |I| = \Theta(n), \]

  that is, there exist constants \(c_1,c_2>0\) such that \(c_1 n \le |I| \le c_2 n\) for all sufficiently large \(n\). Taking logarithms,

  \[ \log_2 |I| - \log_2 c_2 \le \log_2 n \le \log_2 |I| - \log_2 c_1 , \]

  hence \(\log_2 n = \Theta(\log_2 |I|)\) (the additive constants are negligible with respect to \(\log_2 |I|\)).

• Since \(S(n) = \Theta(\log_2 n)\), we obtain \(S(n) = \Theta(\log_2 |I|)\).

If all input values use a fixed constant number of bits, then the worst-case running time of the RecursiveBinarySearch algorithm is

\[ T(|I|) = \Theta(\log |I|). \]

Thus, as the iterative version, the algorithm is logarithmic in the input size: it is not necessary to read the whole input to solve the problem, because the array is sorted.

17.3.5 Space: recursive versus iterative Binary Search

• The recursive and the iterative algorithms execute the same comparisons and have the same worst-case running time. They differ in the memory used.

• Every call that has not yet terminated keeps in memory its own copy of the parameters and local variables (\(left\), \(right\), \(m\), \(mid\), a reference to the array, and the return address). This information is stored in the call stack, and it occupies a constant amount of memory per call.

• In RecursiveBinarySearch no call terminates before its recursive call has terminated. Therefore, when the last call is executing, all the calls of the path are in the call stack. By Observation 17.7, in the worst case there are \(\lfloor \log_2 n \rfloor + 2\) of them, and the extra memory used is

  \[ \Theta(\log n). \]

• The iterative algorithm uses only the variables \(left\), \(right\) and \(mid\): its extra memory is

  \[ \Theta(1). \]

Definition 17.8: tail recursion

A recursive call is a tail call if it is the last operation executed by the calling function, i.e., the value it returns is directly returned by the caller without any further computation. A function whose recursive calls are all tail calls is called tail recursive.

• RecursiveBinarySearch is tail recursive: in lines 10 and 12 the value of the recursive call is returned as it is.

• A tail call can be replaced by updating the parameters and jumping back to the beginning of the function:

  • line 10 becomes \(left \leftarrow mid+1\);

  • line 12 becomes \(right \leftarrow mid-1\);

  • the test of line 2 becomes the condition of a while loop “while \(left \le right\)”.

  The result of this transformation is exactly the iterative BinarySearch algorithm. This is why the two algorithms produce the same sequence of values of \(left\), \(right\) and \(mid\).

• Many compilers perform this transformation automatically (tail-call elimination), so that the recursive version uses only \(\Theta(1)\) extra memory. For instance, the compiler g++ 15.2 removes the recursive calls of a C++ implementation of the algorithm with the option -O2, but not with -O0. However, this is not guaranteed by the C++ standard.

Recursive and iterative Binary Search have the same worst-case running time \(\Theta(\log n)\), but the recursive version uses \(\Theta(\log n)\) extra memory for the call stack, while the iterative version uses \(\Theta(1)\) extra memory. Every tail-recursive algorithm can be transformed into an iterative one.

Key points on the Recursive Binary Search.

• One recursive call on (at most) half of the interval: the call tree is a path, with at most \(\lfloor\log_2 n\rfloor+2\) calls.

• \(S(n)=S(\lfloor n/2\rfloor)+5\), i.e., \(S(n)=5(\lfloor\log_2 n\rfloor+1)+2=\Theta(\log n)\) (case 2 of the Master Theorem with \(a=1\)).

• The algorithm is tail recursive: removing the recursion gives the iterative BinarySearch, with \(\Theta(1)\) extra memory instead of \(\Theta(\log n)\).

17.4 The maximum subarray problem

The last problem of the chapter shows divide and conquer at work on a less obvious problem, where the combine step is the interesting part. It also shows that a recursive algorithm that improves on brute force is not necessarily the best possible one.

17.4.1 Motivation: buying and selling a stock

• Suppose we know in advance the price of a stock for the next days. We may buy one unit of stock once and sell it once, at a later day. We want to maximise the profit (sell price minus buy price).

• This is an example¹: \(p[d]\) is the price at day \(d\), and \(a[d] = p[d]-p[d-1]\) is the daily change of the price.

day \(d\)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
price \(p[d]\)	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
change \(a[d]\)		13	\(-3\)	\(-25\)	20	\(-3\)	\(-16\)	\(-23\)	18	20	\(-7\)	12	\(-5\)	\(-22\)	15	\(-4\)	7

• If we buy at day \(l-1\) and sell at day \(r \ge l\), the profit is

  \[ p[r]-p[l-1] = \big(p[l]-p[l-1]\big) + \big(p[l+1]-p[l]\big) + \cdots + \big(p[r]-p[r-1]\big) = a[l]+a[l+1]+\cdots+a[r], \]

  i.e., the sum of the consecutive daily changes \(a[l..r]\). Hence, maximising the profit is equivalent to finding the consecutive portion of the array \(a[1..16]\) with the largest sum.

• Note that it is not enough to buy at the lowest price or to sell at the highest price: the lowest price (\(63\), day \(7\)) comes after the highest price (\(113\), day \(1\)). In this example the best choice is to buy at day \(7\) (price \(63\)) and sell at day \(11\) (price \(106\)), with profit

  \[ 106 - 63 = 43 = a[8]+a[9]+a[10]+a[11] = 18+20-7+12 . \]

17.4.2 The problem

Given an array \(a[1..n]\) of \(n\) integer numbers, consider the problem of finding two indices \(l \le r\) such that the sum

\[ a[l] + a[l+1] + \cdots + a[r] = \sum_{k=l}^{r} a[k] \]

is maximum. The sub-array \(a[l..r]\) is called a maximum subarray of \(a\).

• A subarray is always non-empty (\(l \le r\)) and made of consecutive elements.

• The problem is interesting only if the array contains negative numbers: if all the entries are non-negative, the whole array \(a[1..n]\) is a maximum subarray. If all the entries are negative, a maximum subarray is made of a single element, the largest one.

• A maximum subarray is not necessarily unique: we look for one of them.

• The number of subarrays of \(a[1..n]\) is the number of pairs \((l,r)\) with \(1 \le l \le r \le n\):

  \[ \sum_{l=1}^{n} (n-l+1) = n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}. \]

17.4.3 A brute force algorithm

• The simplest algorithm considers all the \(n(n+1)/2\) subarrays \(a[l..r]\) and keeps the best one. For a fixed \(l\), the sums of \(a[l..r]\) for \(r = l, l+1, \dots, n\) are computed incrementally: the sum of \(a[l..r]\) is the sum of \(a[l..r-1]\) plus \(a[r]\).

• This is the pseudo-code of the BruteForceMaximumSubarray algorithm:

Algorithm: BruteForceMaximumSubarray

Input: An array \(a[1..n]\) of \(n\) integer numbers

Output: Indices \(bl \le br\) of a maximum subarray and its sum \(best\)

1function BruteForceMaximumSubarray(a, n)

2\(best := a[1]\)

3\(bl := 1\)

4\(br := 1\)

5\(l := 1\)

6while \(l \le n\) do

7\(sum := 0\)

8\(r := l\)

9while \(r \le n\) do

10\(sum \leftarrow sum + a[r]\)// sum of \(a[l..r]\)

11if \(sum > best\) then

12\(best \leftarrow sum\)

13\(bl \leftarrow l\)

14\(br \leftarrow r\)

15end

16\(r \leftarrow r + 1\)

17end

18\(l \leftarrow l + 1\)

19end

20return \((bl, br, best)\)

21end

Run in Colab:PythonC++Java

Example 17.11: brute force algorithm

Consider \(a = [-2, 5, -1, 3]\). The algorithm starts with \(best = a[1] = -2\) and examines the \(4\cdot 5/2 = 10\) subarrays in this order:

\(l\)	\(r\)	\(sum\)	action
1	1	\(-2\)	\(sum \le best = -2\)
1	2	\(3\)	\(sum > best\) \(\Rightarrow\) \(best = 3\), \(bl=1\), \(br=2\)
1	3	\(2\)
1	4	\(5\)	\(sum > best\) \(\Rightarrow\) \(best = 5\), \(bl=1\), \(br=4\)
2	2	\(5\)	\(sum \le best = 5\)
2	3	\(4\)
2	4	\(7\)	\(sum > best\) \(\Rightarrow\) \(best = 7\), \(bl=2\), \(br=4\)
3	3	\(-1\)
3	4	\(2\)
4	4	\(3\)

The algorithm returns \((2,4,7)\): the maximum subarray is \(a[2..4] = [5,-1,3]\) with sum \(7\).

Worst-case running time

• Let \(S(n)\) denote the number of steps executed by BruteForceMaximumSubarray in the worst case, where \(n\) is the size of the array.

• The execution of lines 12–14 depends on the input. We define a function \(t(l,r) \in \{0,1\}\), for \(1 \le l \le r \le n\), where \(t(l,r)=1\) if lines 12–14 are executed when the inner loop examines the pair \((l,r)\), and \(t(l,r)=0\) otherwise.

• For a fixed \(l\), the inner loop executes \(n-l+1\) iterations, and its condition is tested \(n-l+2\) times. Hence

  \[ \sum_{l=1}^{n}(n-l+1) = \frac{n(n+1)}{2}, \qquad \sum_{l=1}^{n}(n-l+2) = \frac{n(n+1)}{2} + n . \]

• The number of times each line of code is executed is:

  • Lines 2, 3, 4, 5 are executed \(1\) time each

  • Line 6 is executed \(n+1\) times

  • Lines 7 and 8 are executed \(n\) times each

  • Line 9 is executed \(\frac{n(n+1)}{2} + n\) times

  • Lines 10, 11 and 16 are executed \(\frac{n(n+1)}{2}\) times each

  • Lines 12, 13, 14 are executed \(\sum_{l=1}^{n}\sum_{r=l}^{n} t(l,r)\) times each

  • Line 18 is executed \(n\) times

  • Line 20 is executed \(1\) time

• Therefore, the total number of steps is

  \[ \begin{aligned} &4 + (n+1) + 2n + \frac{n(n+1)}{2} + n + 3\,\frac{n(n+1)}{2} + n + 1 + 3\sum_{l=1}^{n}\sum_{r=l}^{n} t(l,r)\\[1ex] &= 2n^2 + 7n + 6 + 3\sum_{l=1}^{n}\sum_{r=l}^{n} t(l,r). \end{aligned} \]

  In Example 17.11 there are \(3\) updates and the algorithm executes \(2\cdot 16+7\cdot 4+6+3\cdot 3=75\) steps.

• Since \(0 \le t(l,r) \le 1\), the double sum is between \(0\) and \(n(n+1)/2\). Hence, for every input of size \(n\), the number of steps is between

  \[ 2n^2+7n+6 \qquad\text{and}\qquad 2n^2+7n+6+\frac{3n(n+1)}{2} = \frac{7}{2}n^2 + \frac{17}{2}n + 6 , \]

  and so is the worst-case number of steps \(S(n)\). Both bounds are \(\Theta(n^2)\); for example,

  \[ \lim_{n\to\infty}\frac{2n^2+7n+6}{n^2} = 2 \in \R_{>0}, \qquad \lim_{n\to\infty}\frac{\frac{7}{2}n^2+\frac{17}{2}n+6}{n^2} = \frac{7}{2} \in \R_{>0}. \]

  Therefore,

  \[ S(n) = \Theta(n^2). \]

  Note that, for every input (not only in the worst case), the algorithm executes \(\Theta(n^2)\) steps, since it always examines all the \(n(n+1)/2\) subarrays.

• Under the hypothesis that every entry uses a constant number of bits, \(|I| = \Theta(n)\), and therefore \(S(n) = \Theta(|I|^2)\).

If all input values use a fixed constant number of bits, then the worst-case running time of the BruteForceMaximumSubarray algorithm is

\[ T(|I|) = \Theta(|I|^2). \]

Thus, the brute force algorithm is quadratic in the input size.

17.4.4 A divide and conquer algorithm

• We now design a recursive algorithm based on the divide and conquer approach, as for Merge Sort. We solve the problem on a sub-array \(a[l..r]\), and we initially call it with \(l=1\) and \(r=n\).

• Divide: split \(a[l..r]\) into two halves \(a[l..mid]\) and \(a[mid+1..r]\), where

  \[ mid = \left\lfloor \frac{l+r}{2} \right\rfloor \quad \Big(= l + \left\lfloor \frac{r-l}{2} \right\rfloor\Big). \]

• Every subarray \(a[i..j]\) of \(a[l..r]\) (with \(l \le i \le j \le r\)) is in exactly one of these three situations:

  1. it lies entirely in the left half: \(l \le i \le j \le mid\);

  2. it lies entirely in the right half: \(mid+1 \le i \le j \le r\);

  3. it crosses the midpoint: \(l \le i \le mid < j \le r\).

• Conquer: a maximum subarray of type 1 and of type 2 are found recursively, since they are maximum subarrays of \(a[l..mid]\) and \(a[mid+1..r]\), respectively.

• Combine: a maximum subarray of type 3 is found by a non-recursive procedure, FindMaxCrossingSubarray, described below. The answer is the best of the three subarrays.

Maximum subarray crossing the midpoint

• A subarray crossing the midpoint is made of two parts: \(a[i..mid]\), which ends at \(mid\), and \(a[mid+1..j]\), which starts at \(mid+1\):

  \[ \sum_{k=i}^{j} a[k] = \sum_{k=i}^{mid} a[k] + \sum_{k=mid+1}^{j} a[k] . \]

  The first term depends only on \(i\), the second only on \(j\): the two parts can be chosen independently. Therefore, it is enough to find the best \(i\) (scanning the left half from \(mid\) down to \(l\)) and the best \(j\) (scanning the right half from \(mid+1\) up to \(r\)).

• This is the pseudo-code of the FindMaxCrossingSubarray algorithm (from the same textbook as the stock example):

Algorithm: FindMaxCrossingSubarray

Input: An array \(a\) and three indices \(l \le mid < r\)

Output: Indices \(maxleft \le mid < maxright\) of a maximum subarray crossing the midpoint, and its sum

1function FindMaxCrossingSubarray(a, l, mid, r)

2\(leftsum := -\infty\)

3\(sum := 0\)

4for \(i := mid\) downto \(l\) do

5\(sum \leftarrow sum + a[i]\)// sum of \(a[i..mid]\)

6if \(sum > leftsum\) then

7\(leftsum \leftarrow sum\)

8\(maxleft \leftarrow i\)

9end

10end

11\(rightsum := -\infty\)

12\(sum \leftarrow 0\)

13for \(j := mid+1\) to \(r\) do

14\(sum \leftarrow sum + a[j]\)// sum of \(a[mid+1..j]\)

15if \(sum > rightsum\) then

16\(rightsum \leftarrow sum\)

17\(maxright \leftarrow j\)

18end

19end

20return \((maxleft, maxright, leftsum + rightsum)\)

21end

Run in Colab:PythonC++Java

Lemma 17.9: crossing subarray

Let \(l \le mid < r\). FindMaxCrossingSubarray\((a,l,mid,r)\) returns \((maxleft, maxright, s)\) with \(l \le maxleft \le mid < maxright \le r\) and

\[ s = \sum_{k=maxleft}^{maxright} a[k] = \max\left\{ \sum_{k=i}^{j} a[k] \;:\; l \le i \le mid < j \le r \right\}. \]

Moreover, it executes \(\Theta(n)\) steps, where \(n = r-l+1\).

Proof

Left loop. At the end of the iteration with index \(i\), the variable \(sum\) is equal to \(L(i) = \sum_{k=i}^{mid} a[k]\), and \(leftsum\) is the maximum of \(L(mid), L(mid-1), \dots, L(i)\), attained at \(maxleft\) (by induction on the iterations: at each iteration \(sum\) is compared with the best value found so far, which is initially \(-\infty\), so the first comparison always succeeds). At the end of the loop,

\[ leftsum = \max_{l \le i \le mid} L(i) = L(maxleft). \]

Right loop. In the same way, with \(R(j) = \sum_{k=mid+1}^{j} a[k]\),

\[ rightsum = \max_{mid+1 \le j \le r} R(j) = R(maxright). \]

Combination. For every crossing subarray, \(\sum_{k=i}^{j} a[k] = L(i) + R(j)\). Since \(i\) and \(j\) can be chosen independently,

\[ \max_{l \le i \le mid < j \le r} \big(L(i)+R(j)\big) = \max_{l \le i \le mid} L(i) + \max_{mid < j \le r} R(j) = leftsum + rightsum , \]

which is the value returned, attained by \(a[maxleft..maxright]\).

Running time. The two loops execute \((mid-l+1) + (r-mid) = r-l+1 = n\) iterations in total, each with a constant number of steps (between \(3\) and \(5\) lines, counting the loop test), plus a constant number of steps outside the loops. Hence the number of steps is between \(c_1 n\) and \(c_2 n\) for two constants \(c_1, c_2 > 0\), i.e., \(\Theta(n)\). □

• Note that the crossing subarray always contains both \(a[mid]\) and \(a[mid+1]\), even if they are negative: the subarrays of type 1 and 2 take care of the other cases.

The recursive algorithm

• This is the pseudo-code of the FindMaximumSubarray algorithm. To solve the problem on the whole array we call FindMaximumSubarray\((a,1,n)\).

Algorithm: FindMaximumSubarray

Input: An array \(a\) and two indices \(l \le r\)

Output: Indices \(i \le j\) of a maximum subarray of \(a[l..r]\) and its sum

1function FindMaximumSubarray(a, l, r)

2if \(l = r\) then

3return \((l, r, a[l])\)// Base case: one element

4end

5\(mid := \lfloor (l + r)/2 \rfloor\)

6\((ll, lr, lsum) :=\) FindMaximumSubarray(\(a\), \(l\), \(mid\))

7\((rl, rr, rsum) :=\) FindMaximumSubarray(\(a\), \(mid+1\), \(r\))

8\((cl, cr, csum) :=\) FindMaxCrossingSubarray(\(a\), \(l\), \(mid\), \(r\))

9if \(lsum \ge rsum\) and \(lsum \ge csum\) then

10return \((ll, lr, lsum)\)

11end

12if \(rsum \ge lsum\) and \(rsum \ge csum\) then

13return \((rl, rr, rsum)\)

14end

15return \((cl, cr, csum)\)

16end

Run in Colab:PythonC++Java

• Explanation of the algorithm:

  • Lines 2–3: if the sub-array has only one element, its only subarray is \(a[l..l]\) (base case).

  • Line 5: divide the sub-array into \(a[l..mid]\) and \(a[mid+1..r]\).

  • Lines 6–7: conquer, i.e., find recursively a maximum subarray in each half.

  • Line 8: find a maximum subarray crossing the midpoint.

  • Lines 9–15: combine, i.e., return the best of the three (in case of ties, the left one is preferred, then the right one).

• Differently from the Recursive Binary Search, each call on at least two elements makes two recursive calls: the call tree is a binary tree with \(n\) leaves (one for each element) and \(n-1\) internal nodes, i.e., \(2n-1\) calls in total, exactly as for RecursiveSum (Observation 17.2).

Example

Example 17.12: divide and conquer on the stock example

Consider the array of the daily changes of the stock example:

\[ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} {i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ {a[i]} & 13 & {-3} & {-25} & 20 & {-3} & {-16} & {-23} & 18 & 20 & {-7} & 12 & {-5} & {-22} & 15 & {-4} & 7 \end{array} \]

• Step 1: the call tree. We call FindMaximumSubarray\((a,1,16)\). In the following tree, each node is a call on \(a[l..r]\), written as \([l..r]\), together with the triple \((i,j,s)\) it returns. The \(16\) leaves (calls on one element \([k..k]\), returning \((k,k,a[k])\)) are not drawn.

• Step 2: the results of the calls. For each call on at least two elements, we report the triples returned by the left recursive call, by the right recursive call and by FindMaxCrossingSubarray, and the triple returned (the best of the three).

call	\(mid\)	left	right	crossing	returned
\([1..16]\)	8	\((4,4,20)\)	\((9,11,25)\)	\((8,11,43)\)	\((8,11,43)\)
\([1..8]\)	4	\((4,4,20)\)	\((8,8,18)\)	\((4,5,17)\)	\((4,4,20)\)
\([9..16]\)	12	\((9,11,25)\)	\((14,16,18)\)	\((9,16,16)\)	\((9,11,25)\)
\([1..4]\)	2	\((1,1,13)\)	\((4,4,20)\)	\((1,4,5)\)	\((4,4,20)\)
\([5..8]\)	6	\((5,5,-3)\)	\((8,8,18)\)	\((6,8,-21)\)	\((8,8,18)\)
\([9..12]\)	10	\((9,9,20)\)	\((11,11,12)\)	\((9,11,25)\)	\((9,11,25)\)
\([13..16]\)	14	\((14,14,15)\)	\((16,16,7)\)	\((14,16,18)\)	\((14,16,18)\)
\([1..2]\)	1	\((1,1,13)\)	\((2,2,-3)\)	\((1,2,10)\)	\((1,1,13)\)
\([3..4]\)	3	\((3,3,-25)\)	\((4,4,20)\)	\((3,4,-5)\)	\((4,4,20)\)
\([5..6]\)	5	\((5,5,-3)\)	\((6,6,-16)\)	\((5,6,-19)\)	\((5,5,-3)\)
\([7..8]\)	7	\((7,7,-23)\)	\((8,8,18)\)	\((7,8,-5)\)	\((8,8,18)\)
\([9..10]\)	9	\((9,9,20)\)	\((10,10,-7)\)	\((9,10,13)\)	\((9,9,20)\)
\([11..12]\)	11	\((11,11,12)\)	\((12,12,-5)\)	\((11,12,7)\)	\((11,11,12)\)
\([13..14]\)	13	\((13,13,-22)\)	\((14,14,15)\)	\((13,14,-7)\)	\((14,14,15)\)
\([15..16]\)	15	\((15,15,-4)\)	\((16,16,7)\)	\((15,16,3)\)	\((16,16,7)\)

• Step 3: the crossing computations of the two calls of level 1. Call \([1..8]\), \(mid = 4\):

\(i\)	\(a[i]\)	\(sum\)	\(leftsum\)	\(maxleft\)
4	20	20	20	4
3	\(-25\)	\(-5\)	20	4
2	\(-3\)	\(-8\)	20	4
1	13	5	20	4

\(j\)	\(a[j]\)	\(sum\)	\(rightsum\)	\(maxright\)
5	\(-3\)	\(-3\)	\(-3\)	5
6	\(-16\)	\(-19\)	\(-3\)	5
7	\(-23\)	\(-42\)	\(-3\)	5
8	18	\(-24\)	\(-3\)	5

The crossing subarray is \(a[4..5]\) with sum \(20 + (-3) = 17\). Call \([9..16]\), \(mid = 12\):

\(i\)	\(a[i]\)	\(sum\)	\(leftsum\)	\(maxleft\)
12	\(-5\)	\(-5\)	\(-5\)	12
11	12	7	7	11
10	\(-7\)	0	7	11
9	20	20	20	9

\(j\)	\(a[j]\)	\(sum\)	\(rightsum\)	\(maxright\)
13	\(-22\)	\(-22\)	\(-22\)	13
14	15	\(-7\)	\(-7\)	14
15	\(-4\)	\(-11\)	\(-7\)	14
16	7	\(-4\)	\(-4\)	16

The crossing subarray is \(a[9..16]\) with sum \(20 + (-4) = 16\).

• Step 4: the crossing computation of the first call \([1..16]\), \(mid = 8\):

\(i\)	\(a[i]\)	\(sum\)	\(leftsum\)	\(maxleft\)
8	18	18	18	8
7	\(-23\)	\(-5\)	18	8
6	\(-16\)	\(-21\)	18	8
5	\(-3\)	\(-24\)	18	8
4	20	\(-4\)	18	8
3	\(-25\)	\(-29\)	18	8
2	\(-3\)	\(-32\)	18	8
1	13	\(-19\)	18	8

\(j\)	\(a[j]\)	\(sum\)	\(rightsum\)	\(maxright\)
9	20	20	20	9
10	\(-7\)	13	20	9
11	12	25	25	11
12	\(-5\)	20	25	11
13	\(-22\)	\(-2\)	25	11
14	15	13	25	11
15	\(-4\)	9	25	11
16	7	16	25	11

The crossing subarray is \(a[8..11]\) with sum \(18 + 25 = 43\).

In the first call, the left half gives \(20\), the right half gives \(25\) and the crossing subarray gives \(43\): the algorithm returns \((8,11,43)\), i.e., buy at day \(7\) and sell at day \(11\), with profit \(43\). Note that the optimal subarray is found only at the last step, by FindMaxCrossingSubarray: it is neither in the left half nor in the right half.

17.4.5 Correctness

Theorem 17.10: correctness of FindMaximumSubarray

For every \(l \le r\), FindMaximumSubarray\((a,l,r)\) returns \((i,j,s)\) with \(l \le i \le j \le r\) and

\[ s = \sum_{k=i}^{j} a[k] = \max\left\{ \sum_{k=i'}^{j'} a[k] \;:\; l \le i' \le j' \le r \right\}. \]

Proof

We proceed by strong induction on the number of elements \(n = r-l+1 \ge 1\).

Base case \(n = 1\). Then \(l = r\), the only subarray is \(a[l..l]\), and the algorithm returns \((l,l,a[l])\), which is correct.

Inductive step. Let \(n \ge 2\) and assume (inductive hypothesis) that the statement holds for every sub-array with \(n' < n\) elements. Since \(l < r\), we have \(l \le mid < r\), and the two halves \(a[l..mid]\) and \(a[mid+1..r]\) have \(\lceil n/2 \rceil\) and \(\lfloor n/2 \rfloor\) elements, both at least \(1\) and less than \(n\). By the inductive hypothesis:

• \(lsum\) is the maximum sum of a subarray of type 1 (contained in \(a[l..mid]\)), attained by \(a[ll..lr]\);

• \(rsum\) is the maximum sum of a subarray of type 2 (contained in \(a[mid+1..r]\)), attained by \(a[rl..rr]\).

By Lemma 17.9, \(csum\) is the maximum sum of a subarray of type 3 (crossing the midpoint), attained by \(a[cl..cr]\).

Every subarray of \(a[l..r]\) is of type 1, 2 or 3. Hence the maximum sum of a subarray of \(a[l..r]\) is

\[ \max\{lsum, rsum, csum\}, \]

and lines 9–15 return exactly a triple attaining this maximum. □

17.4.6 Worst-case running time

The recurrence

• Let \(S(n)\) denote the number of steps executed by FindMaximumSubarray in the worst case on a sub-array of \(n = r-l+1\) elements.

• If \(n = 1\), only lines 2–3 are executed: \(S(1) = c_1\), a constant.

• If \(n \ge 2\):

  • lines 2, 5 and 9–15 execute a constant number of steps;

  • the recursive calls of lines 6 and 7 execute \(S(\lceil n/2 \rceil)\) and \(S(\lfloor n/2 \rfloor)\) steps;

  • line 8 executes \(\Theta(n)\) steps (Lemma 17.9).

• Therefore,

  \[ S(n) = \begin{cases} c_1 & \text{if } n = 1,\\[2mm] S\big(\lceil n/2 \rceil\big) + S\big(\lfloor n/2 \rfloor\big) + \Theta(n) & \text{if } n \ge 2. \end{cases} \]

  Ignoring floors and ceilings (which do not change the asymptotic solution), we obtain the same recurrence as Merge Sort:

  \[ S(n) = 2\,S(n/2) + \Theta(n). \]

• Note that the running time does not depend on the values in the array, but only on \(n\): every input of size \(n\) is a worst case.

Solution by the Master Theorem

• Identify \(a\), \(b\), \(f(n)\): \(a = 2\), \(b = 2\), \(f(n) = \Theta(n)\).

• Compute \(n^{\log_b a} = n^{\log_2 2} = n\).

• Compare: \(f(n) = \Theta(n) = \Theta\big(n^{\log_2 2}\log^0 n\big)\).

• Verify the hypothesis: we are in case 2 of the Master Theorem with \(k=0\).

• Conclude:

  \[ S(n) = \Theta\big(n^{\log_2 2}\log^{0+1} n\big) = \Theta(n \log n). \]

Solution by the recursion tree

• Let \(n = 2^k\) be a power of \(2\), and let \(c\,n\) be the cost of the non-recursive part of a call on \(n \ge 2\) elements. In the recursion tree, the level \(h\) (for \(h = 0, 1, \dots, k-1\)) contains \(2^h\) calls on \(n/2^h\) elements each, with total cost

  \[ 2^h \cdot c\,\frac{n}{2^h} = c\,n . \]

  The last level (\(h = k = \log_2 n\)) contains the \(n\) leaves, with total cost \(c_1 n\).

• Summing over all the levels:

  \[ S(n) = \underbrace{c\,n + c\,n + \cdots + c\,n}_{\log_2 n \text{ times}} + c_1 n = c\,n\log_2 n + c_1 n = \Theta(n \log n). \]

• The recursion tree also explains the result: there are \(\log_2 n\) levels and each level costs \(\Theta(n)\), because the crossing computations of the calls of a level scan, all together, the whole array once.

Worst-case running time as a function of the input size

• Under the hypothesis that every entry uses a constant number of bits, \(|I| = \Theta(n)\), and also \(\log n = \Theta(\log |I|)\) (as shown for the Recursive Binary Search). Hence

  \[ S(n) = \Theta(n\log n) = \Theta(|I| \log |I|). \]

If all input values use a fixed constant number of bits, then the worst-case running time of the FindMaximumSubarray algorithm is

\[ T(|I|) = \Theta(|I| \log |I|). \]

Thus, the divide and conquer algorithm is asymptotically faster than the brute force algorithm, whose worst-case running time is \(\Theta(|I|^2)\).

17.4.7 Remark: an iterative linear algorithm

• The divide and conquer algorithm is much better than the brute force algorithm. However, the maximum subarray problem can be solved even faster, with a simple iterative algorithm due to J. Kadane, which scans the array only once.

• Idea: for each position \(i\), let \(M(i)\) be the maximum sum of a subarray ending at position \(i\). A subarray ending at \(i\) is either \(a[i]\) alone, or a subarray ending at \(i-1\) extended with \(a[i]\). Therefore,

  \[ M(1) = a[1], \qquad M(i) = a[i] + \max\{0, M(i-1)\} \quad (i \ge 2). \]

  In words: if the best subarray ending at \(i-1\) has a negative sum, it is better to restart from \(a[i]\); otherwise, it is better to extend it. The answer to the problem is the maximum of \(M(1), \dots, M(n)\).

• This is the pseudo-code of the Kadane algorithm. The variable \(cur\) stores \(M(i)\) and \(cl\) the first index of the corresponding subarray.

Algorithm: Kadane

Input: An array \(a[1..n]\) of \(n\) integer numbers

Output: Indices \(bl \le br\) of a maximum subarray and its sum \(best\)

1function Kadane(a, n)

2\(best := a[1]\);  \(bl := 1\);  \(br := 1\)

3\(cur := a[1]\);  \(cl := 1\)

4\(i := 2\)

5while \(i \le n\) do

6if \(cur < 0\) then

7\(cur \leftarrow a[i]\);  \(cl \leftarrow i\)// restart

8else

9\(cur \leftarrow cur + a[i]\)// extend

10end

11if \(cur > best\) then

12\(best \leftarrow cur\);  \(bl \leftarrow cl\);  \(br \leftarrow i\)

13end

14\(i \leftarrow i + 1\)

15end

16return \((bl, br, best)\)

17end

Run in Colab:PythonC++Java

Lemma 17.11: loop invariant of Kadane

At the beginning of each iteration of the while loop (and when the loop terminates), with current index \(i\):

1. \(cur = \sum_{k=cl}^{i-1} a[k]\) is the maximum sum of a subarray ending at position \(i-1\);

2. \(best = \sum_{k=bl}^{br} a[k]\) is the maximum sum of a subarray of \(a[1..i-1]\).

Proof

Initialization (\(i = 2\)). The only subarray ending at \(1\) is \(a[1..1]\), and it is also the only subarray of \(a[1..1]\): \(cur = best = a[1]\) with \(cl = bl = br = 1\).

Maintenance. Assume the invariant holds at the beginning of the iteration with index \(i\). A subarray ending at \(i\) is either \(a[i..i]\), with sum \(a[i]\), or \(a[k..i]\) with \(k < i\), whose sum is \(\sum_{h=k}^{i-1}a[h] + a[i] \le cur + a[i]\) (by part 1), with equality for \(k = cl\). Hence the maximum sum of a subarray ending at \(i\) is \(\max\{a[i], cur + a[i]\}\), which is \(a[i]\) if \(cur < 0\) and \(cur + a[i]\) otherwise: this is exactly what lines 6–9 compute. So part 1 holds for \(i+1\).

A subarray of \(a[1..i]\) either is a subarray of \(a[1..i-1]\) (best sum: \(best\), by part 2) or ends at \(i\) (best sum: the new \(cur\)). Lines 11–12 keep the larger of the two, so part 2 holds for \(i+1\).

Termination. The loop terminates with \(i = n+1\): by part 2, \(best\) is the maximum sum of a subarray of \(a[1..n]\), attained by \(a[bl..br]\). □

• Running time. The while loop executes \(n-1\) iterations, each with a constant number of steps. Hence \(S(n) = \Theta(n)\) and, if every entry uses a constant number of bits, \(T(|I|) = \Theta(|I|)\). Since any algorithm must read all the entries of the array, no algorithm can be asymptotically faster.

Example 17.13: Kadane algorithm on the stock example

Execution of Kadane on \(a = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]\). Each row reports the values at the end of the iteration with index \(i\) (row \(i=1\): initialization).

\(i\)	\(a[i]\)	action	\(cur\)	\(cl\)	\(best\)	\((bl,br)\)
1	13	initialization	13	1	13	\((1,1)\)
2	\(-3\)	extend	10	1	13	\((1,1)\)
3	\(-25\)	extend	\(-15\)	1	13	\((1,1)\)
4	20	restart (\(cur<0\))	20	4	20	\((4,4)\)
5	\(-3\)	extend	17	4	20	\((4,4)\)
6	\(-16\)	extend	1	4	20	\((4,4)\)
7	\(-23\)	extend	\(-22\)	4	20	\((4,4)\)
8	18	restart (\(cur<0\))	18	8	20	\((4,4)\)
9	20	extend	38	8	38	\((8,9)\)
10	\(-7\)	extend	31	8	38	\((8,9)\)
11	12	extend	43	8	43	\((8,11)\)
12	\(-5\)	extend	38	8	43	\((8,11)\)
13	\(-22\)	extend	16	8	43	\((8,11)\)
14	15	extend	31	8	43	\((8,11)\)
15	\(-4\)	extend	27	8	43	\((8,11)\)
16	7	extend	34	8	43	\((8,11)\)

The algorithm returns \((8,11,43)\), the same maximum subarray found by the divide and conquer algorithm, after a single scan of the array.

Key points on the maximum subarray problem.

• brute force algorithm: \(\Theta(n^2)\);

• divide and conquer algorithm (recursive): \(\Theta(n \log n)\), with the same recurrence as Merge Sort;

• Kadane algorithm (iterative): \(\Theta(n)\).

A recursive divide and conquer algorithm is not necessarily the best possible one: here, a simple iterative algorithm that exploits the structure of the problem (\(M(i)\) depends only on \(M(i-1)\)) is asymptotically faster. We will come back to this lesson in the chapter «Recursive versus iterative algorithms».

17.5 Summary

The four problems of the chapter cover the three typical shapes of a recursive algorithm on arrays: two calls on the halves with constant combination work (sum), two calls on the halves with linear combination work (Merge Sort, maximum subarray), one call on a half (binary search).

recursive algorithm	recurrence	number of steps	extra memory
RecursiveSum	\(S(n)=2S(n/2)+c\)	\(7n-5=\Theta(n)\)	\(\Theta(\log_2 n)\)
RecursiveSumLinear	\(S(n)=S(n-1)+3\)	\(3n-1=\Theta(n)\)	\(\Theta(n)\)
MergeSort	\(S(n)=2S(n/2)+\Theta(n)\)	\(\Theta(n\log_2 n)\)	\(\Theta(n)\)
RecursiveBinarySearch	\(S(n)=S(\lfloor n/2\rfloor)+5\)	\(5(\lfloor\log_2 n\rfloor+1)+2=\Theta(\log_2 n)\)	\(\Theta(\log_2 n)\)
FindMaximumSubarray	\(S(n)=2S(n/2)+\Theta(n)\)	\(\Theta(n\log_2 n)\)	\(\Theta(\log_2 n)\)

• Correctness: always by strong induction on the size of the sub-problem; the non-recursive parts (Merge, FindMaxCrossingSubarray, Kadane) by loop invariants.

• Recursion gives an asymptotic gain only when the work of the combine step, summed over a level, is small compared with what an iterative algorithm does (Merge Sort against the \(\Theta(n^2)\) sorting algorithms). For the sum and the search it gives no gain in time and costs memory; for the maximum subarray the best algorithm is iterative.

---

Exercises on this chapter: Recursive algorithms

Interactive lab

The algorithm of the chapter, one step at a time: move the sliders and press ▶. The same graph full page, with the other ones of the course, is in the interactive lab.

---

1. The example is taken from the textbook of T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Section 4.1. ↩