Chapter_03_Growth_of_Functions/exercises_3.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 Asymptotic notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-1\n",
    "\n",
    "> Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\\Theta$-notation, prove that $\\max(f(n), g(n)) = \\Theta (f(n) + g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$0.5 \\cdot (f(n) + g(n)) \\le \\max(f(n), g(n)) \\le 1 \\cdot (f(n) + g(n))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-2\n",
    "\n",
    "> Show that for any real constants $a$ and $b$, where $b>0$, $(n+a)^b=\\Theta(n^b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $a > 0$, then $(n + a) ^ b < (n + n) ^ b = (2 n)^b = 2^b \\cdot n^b$;\n",
    "\n",
    "If $a < 0$, let $a := -a$, then $(n - a) ^ b > (n - 0.5n) ^ b = (0.5 n)^b = 0.5^b \\cdot n^b$,\n",
    "\n",
    "Since $0.5^b \\cdot n^b \\le (n+a)^b \\le 2^b \\cdot n^b$, therefore $(n+a)^b=\\Theta(n^b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-3\n",
    "\n",
    "> Explain why the statement, \"The running time of algorithm $A$ is at least $O(n^2)$,\" is meaningless."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O$ is an upper bound, which means $A$ could be $\\Omega(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-4\n",
    "\n",
    "> Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $2^{n+1}=O(2^n)$?\n",
    "\n",
    "$1 \\cdot 2^n \\le 2^{n+1} \\le 2 \\cdot 2^n$, thus $2^{n+1}=O(2^n)$.\n",
    "\n",
    "* $2^{2n}=O(2^n)$?\n",
    "\n",
    "$2^{2n} \\le c \\cdot 2^n$\n",
    "\n",
    "$2^n \\le c$ which is impossible, thus $2^{2n} \\ne O(2^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-5\n",
    "\n",
    "> Prove Theorem 3.1.\n",
    "\n",
    "> Theorem 3.1\n",
    ">\n",
    "> For any two function $f(n)$ and $g(n)$, we have $f(n)=\\Theta(g(n))$ if and only if $f(n)=O(g(n))$ and $f(n)=\\Omega(g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$f(n)=O(g(n))$ implies $0 \\le f(n) \\le c_2 g(n)$\n",
    "\n",
    "$f(n)=\\Omega(g(n))$ implies $0 \\le c_1 g(n) \\le f(n)$\n",
    "\n",
    "Thus $c_1 g(n) \\le f(n) \\le c_2 g(n)$, $f(n)=\\Theta(g(n))$, and vice versa."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-6\n",
    "\n",
    "> Prove that the running time of an algorithm is $\\Theta(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\\Omega(g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Theorem 3.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-7\n",
    "\n",
    "> Prove that $o(g(n)) \\cap \\omega(g(n))$ is the empty set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is no $f(n)$ that $f(n) < g(n)$ and $f(n) > g(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1-8\n",
    "\n",
    "> We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions\n",
    ">\n",
    "> $O(g(n,m))=\\{f(n,m)$: there exist positive constants $c$, $n_0$, and $m_0$ such that $0 \\le f(n,m) \\le c g(n,m)$ for all $n \\ge n_0$ or $m \\ge m_0$ $\\}$.\n",
    ">\n",
    "> Give corresponding definitions for $\\Omega(g(n,m))$ and $\\Theta(g(n,m))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Omega(g(n,m))=\\{f(n,m)$: there exist positive constants $c$, $n_0$, and $m_0$ such that $0 \\le c g(n,m) \\le f(n,m)$ for all $n \\ge n_0$ or $m \\ge m_0$ $\\}$.\n",
    "\n",
    "$\\Theta(g(n,m))=\\{f(n,m)$: there exist positive constants $c_1$, $c_2$, $n_0$, and $m_0$ such that $c_1 g(n,m) \\le f(n,m) \\le c_2 g(n,m)$ for all $n \\ge n_0$ or $m \\ge m_0$ $\\}$."
   ]
  }
 ],
 "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
}