3.3 Standard notations and common functions

3.3-1

Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n)+g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n)\cdot g(n)$

$$ \begin{aligned} \forall n_1 \geq n_2: & f(n_1) \geq f(n_2) \And g(n_1) \geq g(n_2)\cr \implies & f(n_1)+g(n_1) \geq f(n_2)+g(n_2)\cr \implies & f(g(n_1) \geq g(n_2)) \geq f(g(n_2))\cr & if \quad f(n) \geq 0 \And g(n) \geq 0\cr \implies & f(g(n_1)\geq g(n_2)\geq 0)\geq f(g(n_2)) \end{aligned} $$

3.3-2

Prove that $\lfloor \alpha n \rfloor +\lceil (1-\alpha )n \rceil = n$ for any integer n and real number $\alpha$ in the range $0 \leq \alpha \leq 1$

$$ \begin{aligned} \lfloor \alpha n \rfloor +\lceil (1-\alpha )n \rceil & = \lfloor \alpha n \rfloor +\lceil -\alpha n\rceil + n\cr &=\lfloor \alpha n \rfloor - \lfloor \alpha n \rfloor +n\cr &=n \end{aligned} $$

3.3-3

Use equation (3.14) or other means to show that $(n+o(n))^k = \Theta(n^k)$ for any real constant k. Conclude that $\lceil n \rceil ^k$ and $\lfloor n \rfloor ^k = \Theta(n^k)$.

$$ \begin{aligned} n^k\leq(n+o(n))^k=n^k(1+\frac {o(n)}n)^k \leq n^k e^{\frac {o(n)}n} \leq en^k\cr \implies (n+o(n))^k = \Theta(n^k)\cr \lceil n \rceil ^k= (n+o(n))^k=\Theta(n^k)\cr \lfloor n \rfloor ^k = (n+o(n))^k=\Theta(n^k)\cr \end{aligned} $$

3.3-4

Prove the following

a. Equation(3.21).

b. Equations(3.26)-(3.28).

c. $\lg(\Theta(n))=\Theta(\lg n)$

• a. $a^{\lg _b c} = a^{\frac {lg _a c}{\lg _a b}}=c^{\lg _b a}$
• b.

$$ \begin{aligned} n! = \sqrt {2\pi n}(\frac n e)^n(1+\Theta(\frac{1}{n}))\cr \forall c>0,\lim_{n \to \infin} \frac {n!=\frac{\sqrt {2\pi n}} {e^n}(1+\Theta(\frac 1 n))n^n} {cn^n} = \lim_{n \to \infin} \frac{\sqrt {2\pi n}} {e^n}(1+\Theta(\frac 1 n)) = 0\cr \implies n!=o(n^n)\text{ (Equation(3.21))}\cr \lim_{n \to \infin} \frac {n!=\frac{\sqrt {2\pi n}} {e^n}(1+\Theta(\frac 1 n))n^n} {2^n} = \lim_{n \to \infin }\sqrt{2\pi n}(1+\Theta(\frac 1 n))(\frac{n}{2e})^n = \infin \cr \implies n! =\omega(n) \text{ (Equation(3.27))}\cr \lg (n!)=n\lg n+ \frac{1}{2}\lg(2\pi n)+n\lg e+\lg(1+\Theta(\frac{1}{n})) = \Theta(n\lg n)\text{ (Equation(3.28))}\cr \end{aligned} $$

• c.

$$ \begin{aligned} \forall f(n) \in \Theta(n)\cr c_3\lg n\leq \lg {c_1 n} \leq \lg(f(n))\leq \lg{c_2 n} \leq c_4\lg n\cr \implies \lg(\Theta(n))=\Theta(\lg n) \end{aligned} $$

3.3-5

Is the function $\lceil \lg n \rceil !$ polynomially bounded? Is the function $\lceil \lg \lg n \rceil !$ polynomially bounded?

Polynomially bounded:$f(n) \leq cn^k \implies \lg(f(n))=ck\lg(n)\implies \lg(f(n))=O(\lg n)$

$$ \begin{aligned} \lg(\lceil \lg n\rceil !)& =\Theta(\lceil \lg n\rceil \lg(\lceil \lg n\rceil))\cr &=\Theta(\lg n \lg(\lg n))\cr &\implies \lceil \lg n\rceil !\text{ is not polynomially bouded}\cr \lg \lceil \lg \lg n \rceil !&=\Theta(\lceil \lg \lg n\rceil \lg\lceil\lg\lg n\rceil)\cr & =O(\lg^2\lg n)\cr & =O(\lg n)\cr & \implies\lceil\lg\lg n\rceil \text{ is Polynomially bounded} \end{aligned} $$

3.3-6

Which is asymptotically larger: $\lg(\lg^{\ast}n)$ or $\lg^{\ast}(\lg n)$?

$$ \begin{aligned} n=2^k\cr \lim_{n\to\infin}\frac{\lg(\lg^{\ast}n)}{\lg^{\ast}(\lg n)}& = \lim_{k\to\infin}\frac{\lg(\lg^{\ast} 2^k)}{\lg^{\ast}(\lg 2^k)}\cr &= \lim_{k\to\infin} \frac{\lg(1+\lg^{\ast}k)}{\lg^{\ast}k}\cr & =\lim_{t\to \infin}\frac{\lg(1+t)}{t}\cr & = 0 \end{aligned} $$ $\lg^{\ast}(\lg n)$ is larger.

3.3-7

Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2 = x + 1$

$$ \begin{aligned} ax^2+bx+c=0\implies x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\cr x^2-x-1=0 \implies x=\frac{1 \pm\sqrt{5}}{2}=\phi \And \hat\phi \end{aligned} $$

3.3-8

prove by induction that the i-th Fibonacci num satisfies the equation $$ F_i = (\phi^i - \hat{\phi}^i)/\sqrt{5} $$ where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate.

For inductive case:

$$ \begin{aligned} & \text{truth: }\phi\hat\phi=-1,\phi+\hat\phi=1\cr \text{assume }:\cr F_{i-1} &= (\phi^{i-1} - \hat{\phi}^{i-1})/\sqrt{5}\cr F_{i} &= (\phi^{i} - \hat{\phi}^{i})/\sqrt{5}\cr \text{then:}\cr F_{i-1}+F_i & =(\phi^{i-1} - \hat{\phi}^{i-1})/\sqrt{5}+(\phi+\hat\phi)(\phi^i - \hat{\phi}^i)/\sqrt{5}\cr & = (\phi^{i+1}-\hat\phi^{i+1})/\sqrt 5+((1+\phi\hat\phi)\phi^{i-1}-(1+\phi\hat\phi)\hat\phi^{i-1})/\sqrt 5\cr & =F_{i+1}\cr \end{aligned} $$

For base case: $$ \begin{aligned} (\phi^{1} - \hat{\phi}^{1})/\sqrt{5}=1=F_1\cr (\phi^{2} - \hat{\phi}^{2})/\sqrt{5}=(\phi^{1}+1 - (\hat{\phi}^{1}+1))/\sqrt{5}=1=F_2\cr \end{aligned} $$

Tips: I will omit details like"assume $F_i$ $F_{i-1}$" and proof of base case from now on for convenience.

3.3-9

Show that $k\lg k = \Theta(n)$ implies $k = \Theta(n/\lg n)$.

$$ \begin{aligned} & k\lg k=\Theta(n)\cr \implies & n=\Theta(k\lg k)\cr \implies & \lg n = \Theta(\lg k + \lg\lg k)=\Theta(\lg k)\cr \implies & n/\lg n = \Theta(k\lg k)/\Theta(\lg k)=\Theta (k)\cr \implies & k = \Theta(n/\lg n) \end{aligned} $$