Published on

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

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

Question

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size, or (b) increase the input size by one?
(a) n2n^2 (b) n3n^3 (c) 100n2100n^2 (d) nlognnlogn (e) 2n2^n

Solution

Algorithm(a)

Size Change - double
(2n)2=4n2=4∗original\begin{align} (2n)^2 &=4n^2\\ &=4*original \end{align}

Ans. Increased by a factor of 4

Size Change - by one
(n+1)2=original+(2n+1)\begin{equation} (n+1)^2=original+(2n+1) \end{equation}

Ans. Increased by 2n+12n+1

Algorithm(b)

Size Change - double
(2n)3=8n3=8∗original\begin{align} (2n)^3 &=8n^3\\ &=8*original \end{align}

Ans. Increased by a factor of 8

Size Change - by one
(n+1)3=original+(3n2+3n+1)\begin{equation} (n+1)^3=original+(3n^2+3n+1) \end{equation}

Ans. Increased by 3n2+3n+13n^2+3n+1

Algorithm(c)

Size Change - double

Same as Algorithm(a)

Size Change - by one

How to think is the same as that for Algorithm(a).

Ans. Increased by 200n+100200n+100

Algorithm(d)

Size Change - double
(2n)log2n=2nlogn+2nlog2=2∗original+2nlog2\begin{align} (2n)log2n &=2nlogn+2nlog2\\ &=2*original+2nlog2 \end{align}

Ans. The Running time is doubled and an additional 2nlog22nlog2 is added.

Size Change - by one
(n+1)log(n+1)=nlog(n+1)+log(n+1)\begin{equation} (n+1)log(n+1)=nlog(n+1)+log(n+1) \end{equation}

Let's think of the range of log(n+1)log(n+1)

n<n+1≤2n(n≥1)n<n+1 \le 2n \qquad (n\ge1)

So,

logn<log(n+1)≤logn+log2(n≥1)logn < log(n+1) \le logn+log2\qquad (n\ge1)

Multiplying nn and Adding log(n+1)log(n+1) to each expressions above introduces:

nlogn+log(n+1)<nlog(n+1)+log(n+1)≤nlogn+nlog2+log(n+1)  ⟹  original+log(n+1)<(n+1)log(n+1)≤original+nlog2+log(n+1)\begin{align} nlogn+log(n+1) &< nlog(n+1)+log(n+1) \\&\le nlogn+nlog2+log(n+1)\\ \implies original+log(n+1) &< (n+1)log(n+1)\\&\le original+nlog2+log(n+1) \end{align}

Ans. Increased by the amount between log(n+1)log(n+1) and nlog2+log(n+1)nlog2+log(n+1).

Algorithm(b)

Size Change - double
2(2n)=(2n)2=original2\begin{align} 2^(2n) &= (2^n)^2\\ &=original^2 \end{align}

Ans. Increased to be the square of the original running time.

Size Change - by one
2(n+1)=2∗(2n)=2∗original\begin{align} 2^(n+1) &= 2*(2^n)\\ &=2*original \end{align}

Ans. Running times is doubled.