Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E2-41'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-41

Question

Consider the following code fragment:

for i=1 to n/2 do
    for j=i to n-i do
        for k=1 to j do
            output ‘‘foobar’’

Assume nn is even. Let T(n)T(n) denote the number of times “foobar” is printed as a function of nn.
(a) Express T(n)T(n) as three nested summations.
(b) Simplify the summation. Show your work.

Solution

(a)

T(n)=∑i=1n2∑j=in−i∑k=1j1\begin{equation} T(n)=\sum_{i=1}^\frac{n}{2}\sum_{j=i}^{n-i}\sum_{k=1}^j1 \end{equation}

(b)

T(n)=∑i=1n2∑j=in−i∑k=1j1=∑i=1n2∑j=in−ij\begin{align} T(n)&=\sum_{i=1}^\frac{n}{2}\sum_{j=i}^{n-i}\sum_{k=1}^j1\\ &=\sum_{i=1}^\frac{n}{2}\sum_{j=i}^{n-i}j \end{align}

Here, we use a new variable j′j':

j′=j−i\begin{equation} j'=j-i \end{equation}

Rethink the expansion of T(n)T(n).

T(n)=∑i=1n2∑j=in−ij=∑i=1n2∑j′=0n−2ij′=∑i=1n2(i+(n−2i)i+12(n−2i)(n−2i+1))=n38(the answer)\begin{align} T(n)&=\sum_{i=1}^\frac{n}{2}\sum_{j=i}^{n-i}j \\ &=\sum_{i=1}^\frac{n}{2}\sum_{j'=0}^{n-2i}j'\\ &=\sum_{i=1}^\frac{n}{2}(i+(n-2i)i+\frac{1}{2}(n-2i)(n-2i+1))\\ &=\frac{n^3}{8} \quad\text{(the answer)} \end{align}