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

Table of Contents

Introduction
Repository
Exercise 2-36
- Question
- Solution
  - Solution for (f)

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

Question

For each pair of expressions (A, B) below, indicate whether A is $O, o, Ω, ω$ , or $Θ$ of B. Note that zero, one, or more of these relations may hold for a given pair; list all correct ones.

\begin{matrix*} &A &B\\ \text{(f)}&\lg{n!}&n\lg{n}\\ \end{matrix*}

Solution

Solution for (f)

[1] First, think about how long range n! is bound by.
$n!$ can be closely related with the simple power of $n$ , because the half amount of terms in $n!$ is larger than $\frac{n}{2}$ .

\begin{equation} (\frac{n}{2})^{\frac{n}{2}} \lt n! \lt n^n \end{equation}

[1-1] Take a logarithm (base 2) of left hand side.

\begin{equation} LHS=\lg{(\frac{n}{2})^{\frac{n}{2}}}=\frac{n}{2}(\lg{n}-1) \end{equation}

For sufficiantly large $n$ , the following holds:

\begin{equation} \frac{n}{2}(\lg{n}-1) \gt \frac{n}{4}\lg{n} \end{equation}

Using (1) and (3),

\begin{align} &\lg{n!} \gt \frac{n}{4}\lg{n}\\ \implies &\lg{n!}=\Omega(n\lg{n}) \end{align}

[1-2] Take a logarithm of right hand side.

\begin{equation} RHS=n\lg{n} \end{equation}

So, the following binding relation is derived:

\begin{equation} \lg{n!}=O(n\lg{n}) \end{equation}

[1-3] Using the results of [1-1, 1-2],

\begin{equation} \lg{n!}=\Theta(n\lg{n}) \end{equation}

[2] Next, think about the relation of dominations.

From the analysis in [1], The binding to $\lg{n!}$ is:

\begin{equation} \frac{n}{4}\lg{n} \lt \lg{n!} \lt n\lg{n} \end{equation}

$\lg{n!}$ is bound by two simple multiple of $n\lg{n}$ and their domination limits (either $\lg{n!}$ is numerator or denominator) does not converge into 0.

So,

\begin{align} \lg{n!} &\ne o(n\lg{n})\\ \lg{n!} &\ne \omega(n\lg{n}) \end{align}

[3]

From [1], [2],
All relations are: $\Theta$