Published on

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

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-4

Question

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using Big Oh notation.

function Conundrum(n)
    r:=0
    for i=1 to n do
        for j=1+1 to n do
            for k=i+j-1 to n do
                r=r+1
    return r

Solution

Let T(n)T(n) denote the number of times r=r+1r=r+1 is executed as a function of n.

T(n)=∑i=1n∑j=i+1n∑k=i+j−1n\begin{equation} T(n)=\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=i+j-1}^{n} \end{equation}

Using k's range, i and j is bounded as follows:

i+j−1≤k≤n  ⟹  i+j≤n+1\begin{align} i+j-1\le k \le n \\ \implies i+j \le n+1 \end{align}

So, we can rewrite T(n)T(n), then

T(n)=∑i=1n∑j=i+1nF(n,i,j)\begin{equation} T(n)=\sum_{i=1}^{n}\sum_{j=i+1}^{n}F(n,i,j) \end{equation} F(n)={n+2−i−jif i+j≤n+10else \begin{equation} F(n)= \begin{cases} n+2-i-j & \quad \text{if } i+j \le n+1\\ 0 & \quad \text{else } \end{cases} \end{equation}

Formula F()F()'s characteristic narrows the j's summation range and erases itself in formula T()T():

T(n)=∑i=1n∑j=i+1n−i+1n+2−i−j\begin{equation} T(n)=\sum_{i=1}^{n}\sum_{j=i+1}^{n-i+1}n+2-i-j \end{equation}

Similarly to k, using j's range, i is bounded as follows:

i+1≤j≤n−i+1  ⟹  i≤n2\begin{align} i+1 \le j \le n-i+1\\ \implies i \le \frac{n}{2} \end{align}

i is integer, so:

i≤⌊n2⌋\begin{equation} i \le \left\lfloor\frac{n}{2}\right\rfloor \end{equation}

The new range introduces:

T(n)=∑i=1⌊n2⌋∑j=i+1n−i+1n+2−i−j⏟T’(n)\begin{equation} T(n)=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\underbrace{\sum_{j=i+1}^{n-i+1}n+2-i-j}_\text{T'(n)} \end{equation}

First reduce the T′(n)T'(n):

T′(n)=∑j=i+1n−i+1(n−i+2)−(∑j=1n−i+1j−∑j=1ij)=12(4i2−4ni−6i+n2+3n+2)\begin{align} T'(n)=\sum_{j=i+1}^{n-i+1}(n-i+2)-(\sum_{j=1}^{n-i+1}j-\sum_{j=1}^{i}j)\\ =\frac{1}{2}(4i^2-4ni-6i+n^2+3n+2) \end{align}

With the result above, reduce T(n)T(n):

T(n)=16⌊n2⌋(4⌊n2⌋2−6n⌊n2⌋−3⌊n2⌋+3n2+3n−1)\begin{equation} T(n)=\frac{1}{6}\left\lfloor\frac{n}{2}\right\rfloor(4\left\lfloor\frac{n}{2}\right\rfloor^2-6n\left\lfloor\frac{n}{2}\right\rfloor-3\left\lfloor\frac{n}{2}\right\rfloor+3n^2+3n-1) \end{equation}

The worst case running time is the order of Θ(n3)\Theta(n^3).