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

Table of Contents

Introduction
Repository
Exercise 2-24
- Question
- Solution

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

Question

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

\begin{matrix} n^\pi &\pi^n &\binom{n}{5} &\sqrt{2^{\sqrt{n}}}\\ \binom{n}{n-4} &2^{\log^4n} &n^{5(\log{n})^2} &n^4\binom{n}{n-4} \end{matrix}

Solution

[1] First, the order of the sequence whose components' order is dominated by a power of a read number is simply the same as the order of their exponent.
And, an expansion of binomial statement produces polynomial.

Think of expanding binomals:

\begin{align} \binom{n}{5}&=\frac{1}{5!}n(n-1)(n-2)(n-3)(n-4)\\ &=\Theta(n^5)\\\\ \binom{n}{n-4}&=\frac{n!}{(n-4)!4!}\\ &=\Theta(n^4)\\\\ n^4\binom{n}{n-4}&=n^4*\Theta(n^4)\\ &=\Theta(n^8) \end{align}

So, the order of them, plus $n^\pi$ ( $3 \lt \pi \lt 4$ ), is:

\begin{equation} n^\pi \lt \binom{n}{n-4} \lt \binom{n}{5} \lt n^4\binom{n}{n-4} \end{equation}

[2] Make the 4th statement easy:

\begin{align} \sqrt{2^{\sqrt{n}}}&=(2^{n^\frac{1}{2}})^{\frac{1}{2}}\\ &=2^{\frac{n^{\frac{1}{2}}}{2}} \end{align}

So the form belongs to more generic form:

\begin{equation} \sqrt{2^{\sqrt{n}}}\in\{x:x=2^{an^b} (a,b\in\mathbb{R})\} \end{equation}

[3] Think of $2^{\log^4n}$ and its range.

Is n^b dominate log^4n?

\begin{align} \lim\limits_{n \to \infty}{\frac{\log^4n}{n^b}}&=\lim\limits_{x \to \infty}((\log{n})*\frac{1}{n^{\frac{b}{4}}})^4\\ &=\lim\limits_{n \to \infty}((\log{(n^{4b})^{\frac{1}{4b}}})*\frac{1}{n^{\frac{b}{4}}})^4\\ &=\lim\limits_{n \to \infty}\frac{1}{(4b)^4}\log{(n^b)^\frac{1}{n^b}} \end{align}

Here we use following well known relationship:

\begin{equation} \lim\limits_{m \to \infty}m^{\frac{1}{m}}=1 \end{equation}

And $\lim\limits_{n \to \infty}{\frac{\log^4n}{n^b}}$ converges:

\begin{align} \lim\limits_{n \to \infty}{\frac{\log^4n}{n^b}}&=\lim\limits_{n \to \infty}\frac{1}{(4b)^4}\log{1}\\ &=0 \end{align}

Therefore, $n^b$ dominate $\log^4n$ .

Meanwhile, for sufficiently large n, $\log^4n$ dominates $\log{n}$ .

So, for sufficiently large n, the following relations hold:

\begin{align} &a_1\log{n}\lt\log^4n\lt a_2n^b\\ \iff &n^{a_1}\lt 2^{\log^4n} \lt 2^{a_2n^b} \quad(a_1,a_2,b\in\mathbb{R}) \end{align}

Comparing the result of [2], we get the following:

\begin{equation} 2^{\log^4n} \lt \sqrt{2^{\sqrt{n}}} \end{equation}

[4] Think of $n^{5(\log{n})^2}$ and its range.

First, set the value as m and take the log of n for both sides.

\begin{align} &m=n^{5(\log{n})^2}\\ \iff &\log_n{m}=5(\log{n})^2 \end{align}

LHS can be rearranged:

\begin{equation} \log_n{m}=\frac{1}{\log{n}*\lg10}\lg{m} \end{equation}

So, combine the results above:

\begin{align} &\lg{m}=5\lg10(\log{n})^3\\ \iff& m=2^{5\lg10(\log{n})^3} \end{align}

$(\log{n})^4$ dominates $(\log{n})^3$ , and $(\log{n})^3$ dominates $\log{n}$ .
So, $n^{5(\log{n})^2}$ can be integrated in [3]'s result:

\begin{equation} n^{a}\lt n^{5(\log{n})^2} \lt 2^{\log^4n} \lt \sqrt{2^{\sqrt{n}}} \quad(a\in\mathbb{R}) \end{equation}

[5] For sufficiently large $n$ , $\pi^n$ is larger than $3^n$ , and $3^n$ is larger than $2^n$ .
so,

\begin{equation} \sqrt{2^{\sqrt{n}}} \lt \pi^n \end{equation}

Using [1] to [5], the order we want is:

\begin{align} &n^\pi \lt \binom{n}{n-4} \lt \binom{n}{5} \lt n^4\binom{n}{n-4} \\ \lt &n^{5(\log{n})^2} \lt 2^{\log^4n} \lt \sqrt{2^{\sqrt{n}}} \lt \pi^n \quad(\text{the answer}) \end{align}