Chapter_03_Growth_of_Functions/problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-1 Asymptotic behavior of polynomials\n",
    "\n",
    "> Let\n",
    "> \n",
    "> $$p(n)=\\sum_{i=0}^d a_i n^i$$,\n",
    "> \n",
    "> where $a_d > 0$, be a degree-$d$ polynomial in $n$, and let $k$ be a constant. Use the definitions of the asymptotic notations to prove the following properties."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. If $k \\ge d$, then $p(n)=O(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$p(n)=\\sum_{i=0}^d a_i n^i \\le \\sum_{i=0}^d a_i n^k$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. If $k \\le d$, then $p(n)=\\Omega(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$p(n)=\\sum_{i=0}^d a_i n^i \\ge \\sum_{i=k}^d a_i n^i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. If $k = d$, then $p(n)=\\Theta(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$p(n)=O(n^k)$ and $p(n)=\\Theta(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. If $k > d$, then $p(n)=o(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$p(n)=\\sum_{i=0}^d a_i n^i < \\sum_{i=0}^d a_i n^k$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. If $k < d$, then $p(n)=\\omega(n^k)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$p(n)=\\sum_{i=0}^d a_i n^i > \\sum_{i=k}^d a_i n^i$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-2 Relative asymptotic growths\n",
    "\n",
    "> Indicate, for each pair of expressions $(A,B)$ in the table below, whether $A$ is $O$, $o$, $\\Omega$, $\\omega$, or $\\Theta$ of $B$. Assume that $k \\le 1$, $\\epsilon > 0$, and $c > 1$ are constants. Your answer should be in the form of the table with \"yes\" or \"no\" written in each box."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| $A$ | $B$ | $O$ | $o$ | $\\Omega$ | $\\omega$ | $\\Theta$ |\n",
    "|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n",
    "| $\\lg^kn$ | $n^\\epsilon$ | yes | yes | no | no | no |\n",
    "| $n^k$ | $c^n$ | yes | yes | no | no | no |\n",
    "| $\\sqrt{n}$ | $n^{\\sin n}$ | no | no | no | no | no |\n",
    "| $2^n$ | $2^{n/2}$ | no | no | yes | yes | no |\n",
    "| $n^{\\lg c}$ | $c^{\\lg n}$ | yes | no | yes | no | yes |\n",
    "| $\\lg(n!)$ | $\\lg(n^n)$ | yes | no | yes | no | yes |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-3 Ordering by asymptotic growth rates\n",
    "\n",
    "> __*a*__. Rank the following functions by order of growth; that is, find an arrangement $g_1, g_2, \\dots ,g_{30}$ of the functions satisfying $g_1 = \\Omega(g2)$, $g_2 = \\Omega(g3)$, $\\dots$ , $g_{29} = \\Omega(g_{30})$. Partition your list into equivalence classes such that functions $f(n)$ and $g(n)$ are in the same class if and only if $f(n) = \\Theta(g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$2^{2^{n+1}}$ $>$ $2^{2^n}$ $>$ $(n+1)!$ $>$ $n!$ $>$ $e^n$ $>$ $n \\cdot 2^n$ $>$ $2^n$ $>$ $(\\frac{3}{2})^n$ $>$ $n^{\\lg \\lg n}$ $=$ $(\\lg n)^{\\lg n}$ $(\\lg n)!$ $>$ $n^3$ $n ^ 2$ $=$ $4^{\\lg n}$ $>$ $n \\ln n$ $>$ $=$ $\\lg(n!)$ $>$ $n$ $=$ $2^{\\lg n}$ $>$ $(\\sqrt{2})^{\\lg n}$ $>$ $2^{\\sqrt{2 \\lg n}}$ $>$ $\\lg^2n$ $>$ $\\ln n$ $>$ $\\sqrt{\\lg n}$ $>$ $\\ln \\ln n$ $>$ $2^{\\lg^\\ast n}$ $>$ $\\lg^\\ast (\\lg n)$ $=$ $\\lg^\\ast n$ $>$ $\\lg(\\lg^\\ast n)$ $>$ $1$ $=$ $n^{1/\\lg n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Give an example of a single nonnegative function $f(n)$ such that for all functions $g_i(n)$ in part (a), $f(n)$ is neither $O(g_i(n))$ nor $\\Omega(g_i(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$n^{\\sin n}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-4 Asymptotic notation properties\n",
    "\n",
    "> Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove each of the following conjectures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. $f(n)=O(g(n))$ implies $g(n)=O(f(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "False, $f(n)=1$, $g(n)=n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. $f(n)+g(n)=\\Theta(\\min(f(n), g(n)))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "False, $f(n)=1$, $g(n)=n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*c*__. $f(n)=O(g(n))$ implies $\\lg(f(n))=O(\\lg(g(n)))$, where $\\lg(g(n)) \\ge 1$ and $f(n) \\ge 1$ for all sufficiently large $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "True.\n",
    "\n",
    "$f(n) \\le cg(n)$\n",
    "\n",
    "$\\lg(f(n)) \\le \\lg c + \\lg g(n) = O(\\lg g(n))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*d*__. $f(n)=O(g(n))$ implies $2^{f(n)}=O(2^{g(n)})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "False, $f(n)=2n$, $g(n)=n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*e*__. $f(n)=O((f(n))^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "False, $f(n)=1/n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*f*__. $f(n)=O(g(n))$ implies $g(n)=\\Omega(f(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "True.\n",
    "\n",
    "$f(n) \\le cg(n)$\n",
    "\n",
    "$ g(n) \\ge \\frac{1}{c}f(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*g*__. $f(n)=\\Theta(f(n/2))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "False, $f(n)=4^n$, $f(n/2)=2^n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*h*__. $f(n)+o(f(n))=\\Theta(f(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "True.\n",
    "\n",
    "$f(n) + o(f(n)) >= f(n) = 1 \\cdot f(n)$\n",
    "\n",
    "$f(n) + o(f(n)) < f(n) + f(n) < 2 \\cdot f(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-5 Variations on $O$ and $\\Omega$\n",
    "\n",
    "> Some authors define $\\Omega$ in a slightly different way than we do; let’s use $\\overset{\\infty}{\\Omega}$ (read \"omega infinity\") for this alternative definition. We say that $f(n) = \\overset{\\infty}{\\Omega}(g(n))$ if there exists a positive constant c such that $f(n) \\ge cg(n) \\ge 0$ for infinitely many integers $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3-6 Iterated functions\n",
    "\n",
    "> We can apply the iteration operator $\\ast$ used in the $\\lg^\\ast$ function to any monotonically increasing function $f(n)$ over the reals. For a given constant $c \\in \\mathbb{R}$, we define the iterated function $f_c^\\ast$ by\n",
    ">\n",
    "> $f_c^\\ast(n)=\\min\\{i \\ge 0: f^{(i)}(n) \\le c\\}$,\n",
    ">\n",
    "> which need not be well defined in all cases. In other words, the quantity $f_c^\\ast(n)$ is the number of iterated applications of the function f required to reduce its argument down to $c$ or less.\n",
    ">\n",
    "> For each of the following functions $f(n)$ and constants $c$, give as tight a bound as possible on $f_c^\\ast(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|$f(n)$|$c$|$f_c^\\ast(n)$|\n",
    "|:-:|:-:|:-:|\n",
    "|$n-1$|0|$\\Theta(n)$|\n",
    "|$\\lg n$|1|$\\Theta(\\lg^\\ast n)$|\n",
    "|$n/2$|1|$\\Theta(\\lg n)$|\n",
    "|$n/2$|2|$\\Theta(\\lg n)$|\n",
    "|$\\sqrt{n}$|2|$\\Theta(\\lg\\lg n)$|\n",
    "|$\\sqrt{n}$|1|not converge|\n",
    "|$n^{1/3}$|2|$\\Theta(\\log_3 \\lg n)$|\n",
    "|$n/\\lg n$|2|$\\omega(\\lg\\lg n) o(\\lg n)$|"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}