Published on

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

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

Question

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

n2nnlg⁡nln⁡nn−n3+7n5lg⁡nnenn2+lg⁡nn22n−1lg⁡lg⁡nn3(lg⁡n)2n!n1+ε  where0<ε<1\begin{matrix} n &2^n &n\lg{n} &\ln{n}\\ n - n^3 + 7n^5 &\lg{n} &\sqrt{n} &e^n\\ n^2 + \lg{n} &n^2 &2^{n−1} &\lg{ \lg{ n}}\\ n^3 &(\lg{ n})^2 &n! &n^{1+ε}\:\:where 0 <ε< 1 \end{matrix}

Solution

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.

So,

n−n3+7n5>n3>n2+lg⁡n=n2>n1+ε>n>n\begin{align*} n - n^3 + 7n^5 \gt n^3 \gt n^2 + \lg{n} = n^2 \gt n^{1+ε} \gt n \gt \sqrt{n} \end{align*}

Next, think of order of exponential functions.
The order of them is determined by the magnitude of its base. And the order of any exponential functions is larger than that of any power of a real number.
So,

en>2n=2n−1>n−n3+7n5\begin{align*} e^n \gt 2^n=2^{n-1} \gt n - n^3 + 7n^5 \end{align*}

Then, think of order of logarithmic functions.
The order of them is determined by the magnitude of its argument. And the order of any power of any logarithmic functions is smaller than that of any power of a real number.
So,

n>(lg⁡n)2>ln⁡n=lg⁡n>lg⁡lg⁡n\begin{align*} \sqrt{n} > (\lg{ n})^2 > \ln{n} = \lg{n} > \lg{ \lg{ n}} \end{align*}

Think of the rest of the terms.
Fron the same analysis above,

nε>lg⁡n>1\begin{align*} n^ε > \lg{n} > 1 \end{align*}

So, multiplying n to each terms derives:

n1+ε>nlg⁡n>n\begin{align*} n^{1+ε} > n\lg{n} > n \end{align*}

To sum up the story so far, the conclusion sequence can be derived.

en>2n=2n−1>n−n3+7n5>n3>n2+lg⁡n=n2>n1+ε>nlg⁡n>n>n>(lg⁡n)2>ln⁡n=lg⁡n>lg⁡lg⁡n(answer)\begin{align*} e^n &\gt 2^n=2^{n-1} \gt n - n^3 + 7n^5 \\ &\gt n^3 \gt n^2 + \lg{n} = n^2 \gt n^{1+ε} \gt n\lg{n} \\ &> n \gt \sqrt{n} > (\lg{ n})^2 > \ln{n} = \lg{n} > \lg{ \lg{ n}}\\ &\text{(answer)} \end{align*}