Published on

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

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

Question

List the functions below from the lowest to the highest order. If any two or more are of the same order, indicate which.

∑i=1niinn(log⁡n)log⁡n2log⁡n2n!2log⁡4nn(log⁡n)2(nn−4)\begin{matrix} \sum_{i=1}^n i^i &n^n &(\log{n})^{\log{n}} &2^{\log{n^2}}\\ n! &2^{\log^4n} &n^{(\log{n})^2} &\binom{n}{n-4} \end{matrix}

Solution

[1] Think of \sum_1^n i^i.

The summertion's last term is nnn^n and each tesm is smaller than ini^n except the last term.
So the following inequation holds.

nn≤∑i=1nii≤∑i=1nin=∑i=1n−1in+nn\begin{equation} n^n \le \sum_{i=1}^n i^i \le \sum_{i=1}^n i^n=\sum_{i=1}^{n-1} i^n+n^n \end{equation}

The RHS of the statement above is fhuther bounded as:

∑i=1n−1in+nn≤(n−1)∗nn−1+nn=2nn−nn−1=Θ(nn)\begin{equation} \sum_{i=1}^{n-1} i^n+n^n \le (n-1)*n^{n-1}+n^n=2n^n-n^{n-1}=\Theta(n^n) \end{equation}

Meanwhile, the order of n^n is apparently Θ(nn)\Theta(n^n).

Therefore, the order we want to derive is:

∑i=1nii=Θ(nn)\begin{equation} \sum_{i=1}^n i^i=\Theta(n^n) \end{equation}

[2] Think of n!n! and its relations with other well-known ordering characters.

The terms in the factorial is less than nn except the first term nn.
So, the following inequation is derived:

n!=n∗(n−1)∗(n−2)⋯<n∗n∗n⋯=nn\begin{equation} n!=n*(n-1)*(n-2)\cdots \lt n*n*n\cdots=n^n \end{equation}

Meanwhile, the terms is greater than 2 except the last one (=1).
So,

n!>2∗2∗2⋯=2n−1=12∗2n\begin{equation} n! \gt 2*2*2\cdots=2^{n-1}=\frac{1}{2}*2^{n} \end{equation}

The relation of order regarding n! is following:

2n<n!<nn\begin{equation} 2^n \lt n! \lt n^n \end{equation}

[3] Then, think of (log⁡n)log⁡n(\log{n})^{\log{n}}.

Compare it with the simple power of n.

na(log⁡n)log⁡n=2alog⁡n(log⁡n)log⁡n=(2alog⁡n)log⁡n(a∈R)\begin{align} \frac{n^a}{(\log{n})^{\log{n}}}&=\frac{2^{a\log{n}}}{(\log{n})^{\log{n}}}\\ &=(\frac{2^a}{\log{n}})^{\log{n}} \quad (a\in\mathbb{R}) \end{align}

The base of the exponentation is smaller than 1 when n>102an \gt 10^{2^a}.
So, for sufficiantly large nn, the following inequation holds.

na<(log⁡n)log⁡n\begin{equation} n^a \lt {(\log{n})^{\log{n}}} \end{equation}

And, log⁡n\log{n} is smaller than n when n≥1n \ge 1.
So, for sufficiantly large nn, the following inequation holds.

(log⁡n)log⁡n<nlog⁡n<n(log⁡n)2\begin{equation} {(\log{n})^{\log{n}}} \lt n^{\log{n}} \lt n^{(\log{n})^2} \end{equation}

Using [1] to [5] and the result of exercise 2-24, the order we want is:

2log⁡n2<(nn−4)<(log⁡n)log⁡n<n(log⁡n)2<2log⁡4n<n!<nn=∑i=1nii\begin{align} &2^{\log{n^2}} \lt \binom{n}{n-4} \lt {(\log{n})^{\log{n}}} \lt n^{(\log{n})^2}\\ &\lt 2^{\log^4n} \lt n! \lt n^n=\sum_{i=1}^n i^i \end{align}