Chapter 2 - Algorithm Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 2: Algorithm Analysis (Completed 15/52: 29%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Notes:\n",
    "\n",
    "TAKING LOGS AND EXPONENTS DOES NOT PRESERVE DOMINANCE RELATIONSHIPS.\n",
    "\n",
    "For example, $n^3$ dominates $n^2$, but $\\log n^3 = 3\\log n$ does NOT dominate $\\log n^2 = 2 \\log n$. \n",
    "\n",
    "Another example, $\\log(n^3) = O(\\log(n^2))$ but $n^3 \\neq O(n^2)$, since $e^{c\\cdot \\log(n^2)} = e^{ \\log(n^{2c})} = n^{2c} \\neq c n^2$.\n",
    "\n",
    "The FUNDAMENTAL reason for this is that $\\log cf(n) \\neq c\\log f(n)$. Same for $\\exp(cf(n))$. So a given $c$ used to show a given dominance relation can't be reused after taking the logarithm or exponent, since the $c$ is no longer a multiplying factor in front of the new function. The transformed inequality WILL HOLD, but it is not with the function you want.\n",
    "\n",
    "A result of this idea (that logs and exps don't preserve dominance relationships) was stated on page 51: \"Logarithms cut any function down to size\", specifically, the log of ANY polynomial is $O(\\lg n)$.\n",
    "\n",
    "Again, logs and exps WILL preserve inequalities, but likely will not preserve dominance relations.\n",
    "\n",
    "This is not true of taking the square: $(c\\cdot f(n))^2 = c^2 \\cdot f^2(n)$. So now $c^2$ is your new \"$c$\".\n",
    "\n",
    "By the way, this is a property called [homogeneity](http://www.wikiwand.com/en/Homogeneous_function), where $f(cx) = c^kf(x)$ for some $k$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "ALSO, it seems that if $f >> g$, then $g = O(f)$ and $f = \\Omega(g)$. HOWEVER, if $g = O(f)$ this does NOT necessarily mean that $f >> g$. For example, $f = \\Theta(g)$ implies $f = O(g)$, $f = \\Omega(g)$, $g = \\Theta(f)$. But neither dominates each other.\n",
    "\n",
    "In other words, $f >> g$ ($f$ dominates $g$) is a stronger statement than $g = O(f)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Program Analysis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 [3]\n",
    "\n",
    "What value is returned by the following function? Express your answer as a\n",
    "function of $n$. Give the worst-case running time using the Big Oh notation.\n",
    "\n",
    "$\\hspace{2em} function \\text{ mystery}(n)$  \n",
    "$\\hspace{4em} r := 0$  \n",
    "$\\hspace{4em} for\\ i := 1\\ to\\ n-1\\ do$  \n",
    "$\\hspace{6em} for\\ j := i+1\\ to\\ n\\ do$  \n",
    "$\\hspace{8em} for\\ k := 1\\ to\\ j\\ do$  \n",
    "$\\hspace{10em} r := r+1$  \n",
    "$\\hspace{4em} \\text{return}(r)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Examining the loops, it is computing (I am not sure if I was required to simplify the expression):\n",
    "$$\\sum_{i=1}^{n-1}\\sum_{j=i+1}^{n}\\sum_{k=1}^{j}1$$\n",
    "$$= \\sum_{i=1}^{n-1}\\sum_{j=i+1}^{n}j$$\n",
    "$$= \\sum_{i=1}^{n-1}  \\left[ \\sum_{j=1}^{n}j - \\sum_{j=1}^{i}j \\right]$$\n",
    "$$\\stackrel{(*)}{=} \\sum_{i=1}^{n-1} \\left[ \\frac{n(n+1)}{2} - \\frac{i(i+1)}{2} \\right]$$\n",
    "$$= \\sum_{i=1}^{n-1} \\left[ \\frac{n(n+1)}{2} \\right] - \\sum_{i=1}^{n-1} \\left[\\frac{i(i+1)}{2} \\right]$$\n",
    "$$= \\frac{n(n+1)}{2} \\sum_{i=1}^{n-1} 1 - \\frac{1}{2} \\sum_{i=1}^{n-1}  \\left[i^2+i \\right]$$\n",
    "$$= \\frac{n(n-1)(n+1)}{2} - \\frac{1}{2} \\sum_{i=1}^{n-1} i - \\frac{1}{2} \\sum_{i=1}^{n-1} i^2 $$\n",
    "$$\\stackrel{(*)}{=} \\frac{n(n-1)(n+1)}{2} - \\frac{1}{2} \\cdot \\frac{n(n-1)}{2} - \\frac{1}{2} \\cdot \\frac{n(n-1)(2(n-1)+1)}{6} $$\n",
    "$$= \\frac{n(n-1)(n+1)}{2} - \\frac{n(n-1)}{4} - \\frac{n(n-1)(2n-1)}{12} $$\n",
    "$$= \\frac{n(n-1)}{12} \\cdot \\left[6(n+1) - 3 - 2n + 1) \\right]$$\n",
    "$$= \\frac{n(n-1)}{12} \\cdot \\left[4n + 4 \\right]$$\n",
    "$$= \\frac{n(n-1)(n+1)}{3}$$\n",
    "\n",
    "\n",
    "($*$) where we use the expressions $\\sum_{i=1}^n i = \\frac{n(n+1)}{2}$ and $\\sum_{i=1}^n i^2 = \\frac{n(n+1)(2n+1)}{6}$ proved earlier in exercises 1.10 and 1.11.\n",
    "\n",
    "The outer loop will run a maximum of $n-1$ times, the next inner loop will run a maximum of $n$ times, and the most inner loop will run a maximum of $n$, for a worst cast running time of $O(n^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 [3]\n",
    "\n",
    "What value is returned by the following function? Express your answer as a\n",
    "function of $n$. Give the worst-case running time using Big Oh notation.\n",
    "\n",
    "$\\hspace{2em} function \\text{ pesky}(n)$  \n",
    "$\\hspace{4em} r := 0$  \n",
    "$\\hspace{4em} for\\ i := 1\\ to\\ n\\ do$  \n",
    "$\\hspace{6em} for\\ j := 1\\ to\\ i\\ do$  \n",
    "$\\hspace{8em} for\\ k := j\\ to\\ i+j\\ do$  \n",
    "$\\hspace{10em} r := r+1$  \n",
    "$\\hspace{4em} \\text{return}(r)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution*:\n",
    "\n",
    "Examining the loops, it is computing:\n",
    "\n",
    "$$\\sum_{i=1}^{n}\\sum_{j=1}^{i}\\sum_{k=j}^{i+j}1$$\n",
    "$$= \\sum_{i=1}^{n}\\sum_{j=1}^{i}[i+1]$$\n",
    "$$= \\sum_{i=1}^{n}\\left[i\\sum_{j=1}^{i}1\\right] + \\sum_{i=1}^{n}\\sum_{j=1}^{i}1$$\n",
    "$$= \\sum_{i=1}^{n}i^2 + \\sum_{i=1}^{n}i$$\n",
    "$$= \\frac{n(n+1)(2n+1)}{6} + \\frac{n(n+1)}{2}$$\n",
    "$$= \\frac{n(n+1)}{6}\\cdot \\left[ 2n + 1 + 3 \\right]$$\n",
    "$$= \\frac{n(n+1)(n+2)}{3}$$\n",
    "\n",
    "The $i$ loop will run n times, the $j$ loop will run at most $n$ times, and the $k$ loop will run at most $n$ times, for a total running times of $O(n^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 [5] Unfinished\n",
    "\n",
    "What value is returned by the following function? Express your answer as a\n",
    "function of $n$. Give the worst-case running time using Big Oh notation.\n",
    "\n",
    "$\\hspace{2em} function \\text{ pestiferous}(n)$  \n",
    "$\\hspace{4em} r := 0$  \n",
    "$\\hspace{4em} for\\ i := 1\\ to\\ n\\ do$  \n",
    "$\\hspace{6em} for\\ j := 1\\ to\\ i\\ do$  \n",
    "$\\hspace{8em} for\\ k := j\\ to\\ i+j\\ do$  \n",
    "$\\hspace{10em} for\\ l := 1\\ to\\ i+j-k\\ do$  \n",
    "$\\hspace{12em} r := r+1$  \n",
    "$\\hspace{4em} \\text{return}(r)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Big Oh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.7 [3]\n",
    "\n",
    "True or False?\n",
    "\n",
    "$\\hspace{1em}$(a): Is $2^{n+1} = O(2^n)$?  \n",
    "$\\hspace{1em}$(b): Is $2^{2n} = O(2^n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Always go back to the definitions on these ones.\n",
    "\n",
    "**(a):**\n",
    "\n",
    "This looks like it would be False, except that this exact problem was covered in the text. It looks misleading because functions like $n^x$ look like $x^n$.\n",
    "\n",
    "$2^{n+1} = 2\\cdot2^n$, which is clearly $O(2^n)$. Specifically, $c \\cdot 2^n > 2 \\cdot 2^n$ for all $n \\geq 1 $ if we set $c=3$. So it's True.\n",
    "\n",
    "**(b):**\n",
    "\n",
    "False. Suppose there is some $c$ such that $2^{2n} \\leq c \\cdot 2^n$ holds for some $n$. Choose $n = \\lg c$. Then the LHS become $2^{2 \\lg c} = 2^{\\lg{c^2}} = c^2$, and the RHS becomes $c \\cdot 2^{\\lg c} = c^2$. Therefore at this particular $n$, $2^{2n} = c \\cdot 2^n$. Furthermore, we can compute the derivatives of each side to show that the LHS is growing faster.\n",
    "\n",
    "LHS: $= \\frac{\\text{d}}{\\text{d}n} \\left[2^{2n}\\right]\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[ \\left( e^{\\ln2} \\right)^{2n} \\right]\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[  e^{2n  \\ln{2}}  \\right] \n",
    "= 2 \\ln{2} \\cdot e^{2n \\ln{2}}\n",
    "= 2 \\ln{2} \\cdot 2^{2n}$ \n",
    "\n",
    "RHS: $= \\frac{\\text{d}}{\\text{d}n} \\left[c \\, 2^n \\right]\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[c \\, e^{n  \\ln{2}} \\right]\n",
    "= c \\ln2 \\cdot e^{n  \\ln{2}}\n",
    "= c \\ln2 \\cdot 2^n$\n",
    "\n",
    "Plugging in $n = \\lg c$, we get $2  c^2 \\ln{2}$ on the LHS, and $c^2 \\ln2$ on the RHS. The LHS derivative is larger. And because of the exponent of $2n$ compared with $n$, it will continue to grow faster.\n",
    "\n",
    "Therefore for any possible $c$ such that $2^{2n} \\leq c \\cdot 2^n$ might hold, we have shown that at $n = \\lg c$ the two sides are equal and that the LHS is growing more rapidly, and will continue to do so. Therefore for $n > \\lg c$ we have $2^{2n} > c \\cdot 2^n$.\n",
    "\n",
    "So $2^{2n} \\neq O(2^n)$. It's False.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.8 [3]\n",
    "\n",
    "For each of the following pairs of functions, either $f(n)$ is in $O(g(n))$, $\\,f(n)$ is in $\\Omega(g(n))$, or $f(n) = \\Theta(g(n))$. Determine which relationship is correct and briefly\n",
    "explain why.\n",
    "\n",
    "$\\hspace{1em}$ (a): $\\, f(n) = \\log n^2; \\, g(n) = \\log n + 5$  \n",
    "$\\hspace{1em}$ (b): $\\, f(n) = \\sqrt n; \\, g(n) = \\log n^2$  \n",
    "$\\hspace{1em}$ (c): $\\, f(n) = \\log^2 n; \\, g(n) = \\log n$  \n",
    "$\\hspace{1em}$ (d): $\\, f(n) = n; \\, g(n) = \\log^2 n$   \n",
    "$\\hspace{1em}$ (e): $\\, f(n) = n\\log n + n; \\, g(n) = \\log n$  \n",
    "$\\hspace{1em}$ (f): $\\, f(n) = 10; \\, g(n) = \\log 10$  \n",
    "$\\hspace{1em}$ (g): $\\, f(n) = 2^n; \\, g(n) = 10n^2$  \n",
    "$\\hspace{1em}$ (h): $\\, f(n) = 2^n; \\, g(n) = 3^n$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):** $\\, f(n) = \\log n^2; \\, g(n) = \\log n + 5$  \n",
    "\n",
    "$\\,f(n)$ can be rewritten as $f(n) = \\log n^2 = 2\\log n$. Therefore $f(n)$ is always within a factor of $2$ of $g(n)$, and constant factors are ignored in Big Oh analysis. So $f(n) = \\Theta(g(n))$.\n",
    "\n",
    "**(b):** $\\, f(n) = \\sqrt n; \\, g(n) = \\log n^2$\n",
    "\n",
    "$\\,g(n) = \\log n^2 = 2 \\log n$, and $\\sqrt n >> \\log n$, so $f(n) = \\Omega(g(n))$. By the way, $\\sqrt n >> \\log n$ is clear when you look at the derivatives: $\\frac{1}{2\\sqrt n} > \\frac{2}{n}$ for $n>16$ since $\\sqrt n$ grows more slowly than $n$.\n",
    "\n",
    "But what about $f(n) = O(g(n))$? Does there exist some $c$ and $n_0$ such that $\\sqrt n \\leq c \\cdot 2\\log n$ for all $n>n_0$? It's easily possible to find the $n$ where the derivatives are equal, above which $\\sqrt n$ grows more rapidly, but this does not guarantee that it will ever overtake $c\\cdot 2\\log n$, especially if $c$ is very large.\n",
    "\n",
    "$f(n) = O(g(n))$ is a statement that $g(n)$ *dominates* $f(n)$, written as $g >> f$. The definition of dominance given on page 56 is that $g$ dominates $f$ if\n",
    "\n",
    "$$ \\lim_{n\\rightarrow \\infty} \\frac{f(n)}{g(n)} = 0$$\n",
    "\n",
    "We can show that $c\\cdot 2\\log n$ does *not* dominate $\\sqrt n$ by showing that $\\sqrt n$ *does* dominate $2\\log n$.\n",
    "\n",
    "$$ \\lim_{n\\rightarrow \\infty} \\frac{g(n)}{f(n)}\n",
    "= \\lim_{n\\rightarrow \\infty} \\frac{2 \\log n}{\\sqrt n}\n",
    "= \\lim_{n\\rightarrow \\infty} \\frac{2 \\log \\sqrt{n}^2}{e^{\\log{\\sqrt n}}}\n",
    "= \\lim_{n\\rightarrow \\infty} \\frac{4 \\log \\sqrt{n}}{e^{\\log{\\sqrt n}}}\n",
    "= 0$$\n",
    "\n",
    "Since the denominator $e^x$ grows much more rapidly than the numerator $x$. Now since this ratio approaches $0$, the reciprocal surely does not, and therefore $c\\cdot 2\\log n$ does not dominate $\\sqrt n$.\n",
    "\n",
    "Therefore $f(n) = \\Omega(g(n))$.\n",
    "\n",
    "**(c):** $\\, f(n) = \\log^2 n; \\, g(n) = \\log n$  \n",
    "\n",
    "$(\\log n)^2 > \\log n$ once $\\log n$ becomes greater than $1$, which occurs once $n$ exceeds $e$. Therefore $\\log^2 n = \\Omega(\\log n)$. $\\log^2 n \\neq O(\\log n)$ since for any $c$, one can find an $n$ such that $\\log^2 n = c \\cdot \\log n$. Specifically, $n = e^c$. Above this, $\\log^2 n > c \\cdot \\log n$.\n",
    "\n",
    "Another way of answering: $x^2$ dominates $x$, and letting $x = \\log n$ won't change that.\n",
    "\n",
    "In an case, we have $\\log^2 n = \\Omega(\\log n)$\n",
    "\n",
    "**(d):** $\\, f(n) = n; \\, g(n) = \\log^2 n$\n",
    "\n",
    "In part (b) we showed that $\\sqrt n = \\Omega(\\log n)$. This means that there exists $c$ and $n_0$ such that $\\sqrt n \\geq c \\cdot \\log n$ holds for all $n > n_0$. Because we know that both sides are positive, we can square both sides to produce $n \\geq c^2 \\cdot\\log^2 n$ for the same $c$, which will hold for all $n > n_0$ for the same $n_0$. Therefore we have $n =  \\Omega(\\log^2 n)$.\n",
    "\n",
    "For the same reason (squaring preserves inequalities), the $n \\neq O(\\log^2 n)$ result from part (b) also applies here.\n",
    "\n",
    "So $n = \\Omega(\\log^2 n)$.\n",
    "\n",
    "**(e):** $\\, f(n) = n\\log n + n; \\, g(n) = \\log n$\n",
    "\n",
    "$n\\log n + n = \\Omega(\\log n)$ since $n\\log n + n> \\log n$ for all $n > 1$.\n",
    "\n",
    "Furthermore $n\\log n + n \\neq O(\\log n)$ since for any $c>0$ we can find an $n_0>0$ such that $n\\log n + n> c \\cdot\\log n$ for all $n>n_0$. Specifically, set $n=c$:\n",
    "\n",
    "$$\\left[n\\log n + n\\right]\\biggr|_{n=c} = c\\log c + c > c\\log c = \\left[ c \\cdot\\log n\\right] \\biggr|_{n=c}$$\n",
    "\n",
    "Therefore, $f(n) = \\Omega(g(n))$.\n",
    "\n",
    "**(f):** $\\, f(n) = 10; \\, g(n) = \\log 10$\n",
    "\n",
    "These are both constants. $f \\geq c \\cdot g$ if $c = (1,000,000)^{-1}$.  On the other hand, $f \\leq c \\cdot g$ if $c = 1,000,000$. Both of these trivially hold for all $n>0$.\n",
    "\n",
    "Therefore $f = \\Theta(g)$.\n",
    "\n",
    "**(g):** $\\, f(n) = 2^n; \\, g(n) = 10n^2$\n",
    "\n",
    "We'll just assume that $2^n >> n^2$. It's obviously true and routinely taken for granted, but also proved in problem 2.11. So we know there exists $c$ and $n_0$ such that $2^n \\geq c \\cdot n^2$ for all $n > n_0$. Let $d = c/10$. Then $2^n \\geq d \\cdot 10n^2$ for all $n>n_0$, and we have shown that $2^n = \\Omega(10n^2)$. Similarly, $2^n \\neq O(10n^2)$ since multiplicative factors don't affect Big Oh analysis, and $2^n \\neq O(n^2)$.\n",
    "\n",
    "So $f(n) = \\Omega(g(n))$.\n",
    "\n",
    "**(h):** $\\, f(n) = 2^n; \\, g(n) = 3^n$\n",
    "\n",
    "$3^n >> 2^n:$\n",
    "\n",
    "$$ \\lim_{n\\rightarrow \\infty} \\frac{2^n}{3^n}\n",
    "= \\lim_{n\\rightarrow \\infty} \\left(\\frac{2}{3}\\right)^n\n",
    "= 0$$\n",
    "\n",
    "since $\\frac{2}{3} < 1$.\n",
    "\n",
    "Since $g$ dominates $f$, $f(n) = O(g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.9 [3]\n",
    "\n",
    "For each of the following pairs of functions $f(n)$ and $g(n)$, determine whether $f(n) = O(g(n))$, $g(n) = O(f(n))$, or both.\n",
    "\n",
    "$\\hspace{1em}$ (a): $\\, f(n) = (n^2 - n)\\,/\\, 2, \\, g(n) = 6n$  \n",
    "$\\hspace{1em}$ (b): $\\, f(n) = n+2\\sqrt n, \\, g(n) = n^2$  \n",
    "$\\hspace{1em}$ (c): $\\, f(n) = n\\log n, \\, g(n) = n\\sqrt n \\, / \\, 2$  \n",
    "$\\hspace{1em}$ (d): $\\, f(n) = n + \\log n, \\, g(n) = \\sqrt n$  \n",
    "$\\hspace{1em}$ (e): $\\, f(n) = 2(\\log n)^2, \\, g(n) = \\log n + 1$  \n",
    "$\\hspace{1em}$ (f): $\\, f(n) = 4n\\log n + n, \\, g(n) = (n^2 - n)/2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):** $\\, f(n) = (n^2 - n)\\,/\\, 2, \\, g(n) = 6n$\n",
    "\n",
    "We can ignore constant factors and lower order terms, so $f(n) = O(n^2)$ and $g(n) = O(n)$. Since $n^2 >> n$ we have $g(n) = O(f(n))$.\n",
    "\n",
    "**(b):** $\\, f(n) = n+2\\sqrt n, \\, g(n) = n^2$\n",
    "\n",
    "Again, we ignore lower order terms, so $f(n) = O(n)$ and we have $f(n) = O(g(n))$.\n",
    "\n",
    "**(c):** $\\, f(n) = n\\log n, \\, g(n) = n\\sqrt n \\, / \\, 2$\n",
    "\n",
    "We can write $g(n) = n^\\frac{3}{2} \\, /\\, 2$, and then show that g>>f:\n",
    "\n",
    "$$\\lim_{n \\rightarrow \\infty} \\frac{f(n)}{g(n)}\n",
    "= \\lim_{n \\rightarrow \\infty} \\frac{n\\log n}{n^\\frac{3}{2} \\, /\\, 2}\n",
    "= \\lim_{n \\rightarrow \\infty} \\frac{2\\log n}{\\sqrt n}\n",
    "= 0$$\n",
    "\n",
    "since $n^r$ for any positive $r$ will grow much faster than $\\log n$. This was also showed in 2.8(b).\n",
    "\n",
    "Therefore $g >> f$ and so $f(n) = O(g(n))$.\n",
    "\n",
    "**(d):** $\\, f(n) = n + \\log n, \\, g(n) = \\sqrt n$\n",
    "\n",
    "Again, ignoring lower order terms we have $f(n) = O(n)$ (since $n >> \\log n$), and because $n >> \\sqrt n$ we have $g(n) = O(f(n))$.\n",
    "\n",
    "**(e):** $\\, f(n) = 2(\\log n)^2, \\, g(n) = \\log n + 1$\n",
    "\n",
    "Ignoring constant factors and terms, we have $f(n) \\sim (\\log n)^2$ and $g(n) \\sim \\log n$. Because $g\\,/\\,f \\sim 1\\,/\\,\\log n \\rightarrow 0$ as $n \\rightarrow \\infty$, we have $f >> g$ and therefore $g(n) = O(f(n))$.\n",
    "\n",
    "**(f):** $\\, f(n) = 4n\\log n + n, \\, g(n) = (n^2 - n)/2$\n",
    "\n",
    "Again, ignoring constant factors and lower order terms, we have $f \\sim n\\log n$ and $g \\sim n^2$. We then know that $f\\,/\\,g = \\log n \\,/\\, n \\rightarrow 0$ as $n \\rightarrow \\infty$ since $n >>\\log n$. Therefore $g>>f$ and $f(n) = O(g(n))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.10 [3]\n",
    "\n",
    "Prove that $n^3 -3n^2 -n +1 = \\Theta(n^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "First let's calculate the derivatives, which will will need.\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} \\text{LHS}\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[ n^3 - 3n^2 - n + 1\\right]\n",
    "= 3n^2 -6n -1$\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} \\text{RHS}\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[c \\cdot n^3\\right]\n",
    "= c \\cdot 3n^2$\n",
    "\n",
    "Note that for $n>0$, $\\frac{\\text{d}}{\\text{d}n} \\text{LHS} < \\frac{\\text{d}}{\\text{d}n} \\text{RHS}$. This means that (with $c=1$) the RHS will always be growing faster. Furthermore,\n",
    "$\\text{LHS}(n=1) = 1 - 3 - 1 + 1 = -2$\n",
    "while\n",
    "$\\text{RHS}(n=1) = 1$.\n",
    "So at $n=1$, $\\text{RHS} > \\text{LHS}$ and $\\text{RHS}$ will continue to grow more rapidly.\n",
    "\n",
    "This means that if we let $c=1$ and $n_0 = 1$, then $n^3 - 3n^2 - n + 1 < c \\cdot n^3$ for all $n > n_0$.\n",
    "\n",
    "We have therefore shown that $n^3 - 3n^2 - n + 1 = O(n^3)$.\n",
    "\n",
    "Now to demonstrate $\\Omega$, and therefore $\\Theta$, we need to provide numbers $c$ and $n_0$ such that $n^3 - 3n^2 - n + 1 > c \\cdot n^3$ for all $n>n_0$. Let $n_0=100$ and $c = \\frac{1}{3}$.\n",
    "\n",
    "At $n_0$ the RHS is\n",
    "\n",
    "$\\text{RHS}(n=100) = 1,000,000 - 30,000 - 100 + 1 = 970,000 - 100 + 1 = 969,900 + 1 = 969,901$\n",
    "\n",
    "and the LHS is\n",
    "\n",
    "$\\text{LHS}(n=100) = \\frac{1}{3}1,000,000 \\approx 333,333$\n",
    "\n",
    "So at $n=n_0$, $\\text{LHS} > \\text{RHS}$. Their derivatives at $n_0$ evaluate to\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} \\text{LHS} \\biggr|_{n=100}\n",
    "= 30,000 - 600 - 1\n",
    "= 29,399$\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} \\text{RHS} \\biggr|_{n=100}\n",
    "= 10,000$\n",
    "\n",
    "So at $n=n_0$, $\\text{LHS} > \\text{RHS}$ and the LHS is growing more rapidly. A look at the second derivatives\n",
    "$\\left(6n-6, 2n\\right)$ shows that the LHS will continue to grow more rapidly for all $n>n_0$\n",
    "\n",
    "Therefore with $c=\\frac{1}{3}$ $n_0 = 100$, $n^3 - 3n^2 - n + 1 > c \\cdot n^3$ for all $n>n_0$. So $n^3 - 3n^2 - n + 1 = \\Omega(n^3)$.\n",
    "\n",
    "Because $n^3 - 3n^2 - n + 1 = O(n^3)$ and $n^3 - 3n^2 - n + 1 = \\Omega(n^3)$, we have $n^3 - 3n^2 - n + 1 = \\Theta(n^3)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.11 [3]\n",
    "\n",
    "Prove that $n^2 = O(2^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution*:\n",
    "\n",
    "The answer is yes. $2^n$ dominates any polynomial.\n",
    "\n",
    "Let $c=1$. We shall find an $n_0$ such that for all $n>n_0$, $2^n \\geq n^2$.\n",
    "\n",
    "First let's look at some values.\n",
    "\n",
    "$\\hspace{3em} (n^2, 2^n)$  \n",
    "$n=1: \\,(1,\\, 2)$  \n",
    "$n=2: \\,(4,\\, 4)$  \n",
    "$n=3: \\,(9,\\, 8)$  \n",
    "$n=4: \\,(16,\\, 16)$  \n",
    "$n=5: \\,(25,\\, 32)$  \n",
    "$n=6: \\,(36,\\, 64)$  \n",
    "$n=7: \\,(49,\\, 128)$  \n",
    "$n=8: \\,(64,\\, 256)$  \n",
    "$n=9: \\,(81,\\, 512)$  \n",
    "$n=10: \\,(100,\\, 1024)$  \n",
    "\n",
    "Note that at $n=3$, $n^2 > 2^n$, but at $n=4$ they are equal. And for $n>4$ it seems that $2^n > n^2$. So let's set $n_0 = 4$.\n",
    "\n",
    "To prove that $2^n > n^2$ we are going to look at their derivatives at that point and beyond.\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} n^2 = 2n$\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} 2^n\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[\\left( e^{\\ln2} \\right)^n \\right]\n",
    "= \\frac{\\text{d}}{\\text{d}n} \\left[ e^{n\\ln2} \\right]\n",
    "= \\ln2 \\left[ e^{n\\ln2} \\right]\n",
    "= \\ln2 \\cdot2^n$\n",
    "\n",
    "Setting $n = 4$ we have\n",
    "\n",
    "$\\frac{\\text{d}}{\\text{d}n} n^2\\biggr|_{n=4}\n",
    " = 2n\\biggr|_{n=4}= 2(4) = 8$  \n",
    "$\\frac{\\text{d}}{\\text{d}n} 2^n\\biggr|_{n=4}\n",
    " = \\ln2 \\cdot2^n\\biggr|_{n=4}\n",
    " = \\ln2 \\cdot2^4\n",
    " = 16\\ln2\n",
    " \\approx 11$\n",
    "\n",
    "So at $n=4$, $2^n$ is growing faster than $n^2$.\n",
    "\n",
    "Furthermore, the second derivative of $n^2$ is $2$, a constant. And its third derivative is 0. Growth in the slope is constant.\n",
    "\n",
    "On the other hand, the $n$th derivative of $2^n$ is $(\\ln2)^{n}2^n$. The constant factor in front only gets larger. This implies that this function only continues accelerating, faster and faster.\n",
    "\n",
    "Together, these results show that at $n=4$, $n^2 = 2^n$. But $2^n$ is growing more rapidly, and will continue to do so for all $n>4$. Therefore for all $n>4$, $2^n > 2^n$, and therefore $n^2 = O(2^n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.12 [3]\n",
    "\n",
    "For each of the following pairs of functions $f(n)$ and $g(n)$, give an appropriate positive constant $c$ such that $f(n) \\leq c \\cdot g(n)$ for all $n>1$.\n",
    "\n",
    "$\\hspace{1em}$ (a): $\\, f(n) = n^2 + n + 1, \\, g(n) = 2n^3$  \n",
    "$\\hspace{1em}$ (b): $\\, f(n) = n\\sqrt n + n^2, \\, g(n) = n^2$  \n",
    "$\\hspace{1em}$ (c): $\\, f(n) = n^2 - n + 1, \\, g(n) = n^2\\,/\\,2$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Our approach will be to choose $c$ such that $f \\leq c\\cdot g$ at $n=1$, but also that $\\,f' \\leq c\\cdot g'$, and $\\, f'' \\leq c\\cdot g''$ so that $c \\cdot g$ will continue to be greater than $f$ for all larger $n$.\n",
    "\n",
    "**(a):** $\\, f(n) = n^2 + n + 1, \\, g(n) = 2n^3$  \n",
    "\n",
    "Letting $c=2$ so that $g(n) = 4n^3$, the first and second derivatives of $f$ and $g$ are:\n",
    "\n",
    "$f'(n) = 2n + 1; \\, f''(n) = 2 $  \n",
    "$g'(n) = 12n^2; \\, g''(n) = 24n$\n",
    "\n",
    "Plugging in $n=1$ we have\n",
    "\n",
    "$f(1) = 3; \\, f'(1) = 3; \\, f''(1) = 2$  \n",
    "$g(1) = 4; \\, g'(1) = 12; \\, g''(1) = 24$\n",
    "\n",
    "We see that at $n=1$, $\\, f(n) < c \\cdot g(n)$ and that all orders of derivatives are also higher for the RHS. Therefore $\\, f(n) < c \\cdot g(n)$ holds for $n=1$ and will continue to hold for all $n>1$.\n",
    "\n",
    "\n",
    "**(b):** $\\, f(n) = n\\sqrt n + n^2, \\, g(n) = n^2$  \n",
    "\n",
    "Letting $c=2$ so that $g(n) = 2n^2$, the first and second derivatives of $f$ and $g$ are:\n",
    "\n",
    "$f'(n) = \\frac{3}{2}n^{\\frac{1}{2}} + 2n; \\, f''(n) = \\frac{3}{4\\sqrt n} + 2$  \n",
    "$g'(n) = 4n; \\, g''(n) = 4$\n",
    "\n",
    "Plugging in $n=1$ we have\n",
    "\n",
    "$f(1) = 2; \\, f'(1) = \\frac{7}{2}; \\, f''(1) = \\frac{11}{4}$  \n",
    "$g(1) = 2; \\, g'(1) = 4; \\, g''(1) = 4$\n",
    "\n",
    "We see that at $n=1$, $\\, f(n) = c \\cdot g(n)$, but the first and second derivatives on the RHS are greater. Further, the second derivative on the LHS will only get smaller, while the second derivative on the RHS is constant.\n",
    "\n",
    "Together these ensure that $\\, f(n) < c \\cdot g(n)$ for all $n>1$.\n",
    "\n",
    "\n",
    "**(c):** $\\, f(n) = n^2 - n + 1, \\, g(n) = n^2\\,/\\,2$  \n",
    "\n",
    "Letting $c=4$ so that $g(n) = 2n^2$, the first and second derivatives of $f$ and $g$ are:\n",
    "\n",
    "$f'(n) = 2n - 1; \\, f''(n) = 2$  \n",
    "$g'(n) = 4n; \\, g''(n) = 4$\n",
    "\n",
    "Plugging in $n=1$ we have\n",
    "\n",
    "$f(1) = 1; \\, f'(1) = 1; \\, f''(1) = 2$  \n",
    "$g(1) = 2; \\, g'(1) = 4; \\, g''(1) = 4$\n",
    "\n",
    "We see that $n=1$, $\\, f(n) < c \\cdot g(n)$. Further, the first and second derivatives of the RHS are greater than those of the left, and all higher order derivatives are zero. Thie ensures that $\\, f(n) < c \\cdot g(n)$ will continue to hold for all $n>1$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.32 [5]\n",
    "\n",
    "Prove that:\n",
    "$$1^2 - 2^2 + 3^2 - 4^2 + \\ldots + (-1)^{k-1}k^2 = (-1)^{k-1}\\frac{k(k+1)}{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "We'll prove this with induction.\n",
    "\n",
    "*Base case:* $n = 0$.  \n",
    "Both sides are 0.\n",
    "\n",
    "*Base case:* $n = 1$.  \n",
    "LHS: $1^2 = 1$  \n",
    "RHS: $(-1)^{1-1}\\frac{1(1+1)}{2} = (-1)^{0}\\frac{2}{2} = 1 \\cdot 1 = 1$  \n",
    "They are equal.\n",
    "\n",
    "*General case:* $k = n$.\n",
    "\n",
    "Suppose the equation holds for all $k \\leq n - 1$. We would like to show that it holds for $k = n$.\n",
    "\n",
    "$$1^2 - 2^2 + 3^2 - 4^2 + \\ldots + (-1)^{n-1}n^2$$\n",
    "$$\\hspace{1em} = \\sum_{i=1}^{n} (-1)^{i-1}i^2$$\n",
    "$$\\hspace{1em} = (-1)^{n-1}n^2 + \\sum_{i=1}^{n-1} (-1)^{i-1}i^2$$\n",
    "$$\\hspace{1em} = (-1)^{n-1}n^2 + (-1)^{n-2}\\frac{n(n-1)}{2}$$\n",
    "$$\\hspace{1em} = \\frac{(-1)^{n-2}}{2} \\cdot \\left[(-1)^{1}2n^2 + n(n-1)\\right]$$\n",
    "$$\\hspace{1em} = \\frac{(-1)^{n-2}}{2} \\cdot \\left[-2n^2 + n^2-n\\right]$$\n",
    "$$\\hspace{1em} = \\frac{(-1)^{n-2}}{2} \\cdot \\left[-n^2 - n\\right]$$\n",
    "$$\\hspace{1em} = \\frac{(-1)^{n-2}}{2} \\cdot (-1)^1(n^2 + n)$$\n",
    "$$\\hspace{1em} = (-1)^{n-1}\\frac{n(n+1)}{2}$$\n",
    "\n",
    "which is the expression we wanted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.33 [5]\n",
    "\n",
    "Find an expression for the sum of the $i$th row of the following triangle, and prove its correctness. Each entry is the sum of the three entries directly above it. All non existing entries are considered 0.\n",
    "\n",
    "$$ \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_1 \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ $$\n",
    "$$ \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_1 \\hspace{2em} \\_1 \\hspace{2em} \\_1 \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ $$\n",
    "$$ \\_\\_ \\hspace{2em} \\_\\_ \\hspace{2em} \\_1 \\hspace{2em} \\_2 \\hspace{2em} \\_3 \\hspace{2em} \\_2 \\hspace{2em} \\_1 \\hspace{2em} \\_\\_ \\hspace{2em} \\_\\_ $$\n",
    "$$ \\_\\_ \\hspace{2em} \\_1 \\hspace{2em} \\_3 \\hspace{2em} \\_6 \\hspace{2em} \\_7 \\hspace{2em} \\_6 \\hspace{2em} \\_3 \\hspace{2em} \\_1 \\hspace{2em} \\_\\_ $$\n",
    "$$ \\_1 \\hspace{2em} \\_4 \\hspace{2em} 10 \\hspace{2em} 16 \\hspace{2em} 19 \\hspace{2em} 16 \\hspace{2em} 10 \\hspace{2em} \\_4 \\hspace{2em} \\_1 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution*:\n",
    "\n",
    "The sums of the rows in the triangle above are 1, 3, 9, 27, and 81. This suggests that sum of the values in the $i$th row is $3^{i-1}$. Let's prove it.\n",
    "\n",
    "First note that the value in position $A[i,j]$ where $i>0$ and $j \\in \\mathbb{Z}$ is \n",
    "\n",
    "$$A[i,j] = A[i-1,j-1] + A[i-1,j] + A[i-1,j+1] = \\sum_{k=j-1}^{j+1}A[i-1,k]$$\n",
    "\n",
    "that is, the sum of the surrounding values in the previous row.\n",
    "\n",
    "Now let's show that the sum of the elements in row $i$, $\\text{Sum}[i]$ is equal to 3 times the sum in the previous row.\n",
    "\n",
    "$$\\text{Sum}[i] = \\sum_{j=-\\infty}^{\\infty}A[i,j]$$\n",
    "$$= \\sum_{j=-\\infty}^{\\infty} \\bigr[ A[i-1,j-1] + A[i-1,j] + A[i-1,j+1] \\bigr]$$\n",
    "$$= \\sum_{j=-\\infty}^{\\infty}  A[i-1,j-1] + \\sum_{j=-\\infty}^{\\infty}   A[i-1,j] + \\sum_{j=-\\infty}^{\\infty} A[i-1,j+1] $$\n",
    "$$= \\text{Sum}[i-1] + \\text{Sum}[i-1] + \\text{Sum}[i-1]$$\n",
    "$$= 3\\cdot \\text{Sum}[i-1] $$\n",
    "\n",
    "Now we can use recursion to find a closed form solution.\n",
    "\n",
    "Base case: $n=1$.  \n",
    "Row $1$ consists of all $0$s except for a single $1$ in position $j=0$. Therefore $\\text{Sum}[1] = 1$.\n",
    "\n",
    "General case.  \n",
    "Suppose $\\text{Sum}[i] = 3^{i-1}$ for all $i<n$. Then we have\n",
    "\n",
    "$$\\text{Sum}[n] = 3\\cdot \\text{Sum}[n-1] =  3\\cdot 3^{n-2} = 3^{n-1}$$\n",
    "\n",
    "Therefore we have shown that the sum of the elements in the $i$th row is $3^{i-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.34 [3]\n",
    "\n",
    "Assume that Christmas has $n$ days. Exactly how many presents did my “true\n",
    "love” send me? (Do some research if you do not understand this question.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "On the first day of Christmas I received 1 present.  \n",
    "On the second day of Christmas I received $2+1 = 3$ presents.  \n",
    "On the thrids day of Christmas I received $3+2+1 = 6$ presents.  \n",
    "\n",
    "On the $n$th day of Christmas I received $\\sum_{i=1}^{n}i = \\frac{n(n+1)}{2}$ presents.\n",
    "\n",
    "BY the $n$th day of Christmas I received\n",
    "\n",
    "$$\\sum_{m=1}^{n}\\frac{m(m+1)}{2}\n",
    "= \\frac{1}{2}\\sum_{m=1}^{n} m^2 + \\frac{1}{2}\\sum_{m=1}^{n}m$$\n",
    "$$= \\frac{n(n+1)(2n+1)}{12} + \\frac{n(n+1)}{4}$$\n",
    "$$= \\frac{n(n+1)}{12}\\cdot \\left[ 2n+1 + 3 \\right]$$\n",
    "$$= \\frac{n(n+1)}{12}\\cdot 2\\left[ n+2 \\right]$$\n",
    "$$= \\frac{n(n+1)(n+2)}{6}$$\n",
    "\n",
    "So if Christmas is n days long I receive a total of $\\frac{n(n+1)(n+2)}{6}$ gifts.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logarithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.39 [5]\n",
    "\n",
    "Prove the following identities on logarithms:  \n",
    "$\\hspace{1em}$ (a): Prove that $\\, \\log_{a}{(xy)} = \\log_{a}{x} + \\log_{a}{y}$  \n",
    "$\\hspace{1em}$ (b): Prove that $\\, \\log_{a}{x^y} = y \\log_{a}{x}$  \n",
    "$\\hspace{1em}$ (c): Prove that $\\, \\log_{a}{x} = \\frac{\\log_{b}{x}}{\\log_{b}{a}}$  \n",
    "$\\hspace{1em}$ (d): Prove that $\\, x^{\\log_{b}{y}} = y^{\\log_{b}{x}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**(a):**  \n",
    "Because $n^x$  with $n > 0$ is 1 to 1 (bijective) from $\\mathbb{R} \\rightarrow \\mathbb{R}^+$ and therefore has the inverse function $\\log_n{x}$, if we can show that $a^{\\text{LHS}} = a^{\\text{RHS}}$, then $\\text{LHS} = \\text{RHS}$.\n",
    "\n",
    "Raising $a$ to both sides:  \n",
    "$a^\\text{LHS} = a^{\\log_{a}{(xy)}} = xy$  \n",
    "$a^\\text{RHS} = a^{\\log_{a}{x} + \\log_{a}{y}}\n",
    "= a^{\\log_{a}{x}} \\cdot a^{\\log_{a}{y}} = xy$  \n",
    "\n",
    "They are equal, so $\\text{LHS} = \\text{RHS}$.\n",
    "\n",
    "**(b):**  \n",
    "$\\log_{a}{x^y}$  \n",
    "$\\hspace{1em} = \\log_{a}\\left[ x\\cdot x \\cdot \\ldots \\{ \\text{y times} \\}\n",
    "\\ldots \\cdot x \\right]$  \n",
    "$\\hspace{1em} = \\log_{a}x + \\log_{a}x + \\ldots \\{\\text{y times}\\} \\ldots + \\log_{a}x$  \n",
    "$\\hspace{1em} = y \\log_{a}x$\n",
    "\n",
    "Alternatively,  \n",
    "$a^\\text{LHS} = a^{\\log_{a}{x^y}} = x^y$  \n",
    "$a^\\text{RHS}$\n",
    "$= a^{y \\log_{a}{x}}$\n",
    "$ = \\left(a^{\\log_{a}{x}}\\right)^y$\n",
    "$= x^y$\n",
    "\n",
    "So $a^\\text{LHS} = a^\\text{RHS}$, and therefore $\\text{LHS} = \\text{RHS}$ (since $a^x$ is injective).\n",
    "\n",
    "**(c):**  \n",
    "$$\\log_{a}{x} = \\frac{\\log_{b}{x}}{\\log_{b}{a}}$$\n",
    "Multiply both sides by $\\log_{x}{a}$:\n",
    "$$\\log_{a}{x} \\cdot \\log_{b}{a} = \\log_{b}{x}$$\n",
    "We can rewrite the LHS as:  \n",
    "$$\\text{LHS} = \\log_{a}{x} \\cdot \\log_{b}{a}  =  \\log_{b}{a^{\\log_{a}{x}}} = \\log_{b}{x} = \\text{RHS}$$  \n",
    "So they are equal.\n",
    "\n",
    "**(d):**  \n",
    "Raising both sides to $\\frac{1}{\\log_bx}$, on the LHS we have\n",
    "\n",
    "$$ \\text{LHS}^{\\frac{1}{\\log_bx}}\n",
    "= \\left(x^{\\log_by}\\right)^{\\frac{1}{\\log_bx}}\n",
    "= x^{\\frac{\\log_by}{\\log_bx}} = x^{\\log_xy}\n",
    "= y$$\n",
    "\n",
    "and on the RHS we have\n",
    "\n",
    "$$ \\text{RHS}^{\\frac{1}{\\log_bx}}\n",
    " = \\left(y^{\\log_bx}\\right)^{\\frac{1}{\\log_bx}}\n",
    " = y^{\\frac{\\log_bx}{\\log_bx}}\n",
    " = y$$\n",
    "\n",
    "So $\\text{LHS}^\\frac{1}{\\log_bx} = \\text{RHS}^\\frac{1}{\\log_bx}$. Now because $f(x) = x^n$ and $f^{-1}(x) = x^{1/n}$ are 1 to 1 inverse operations, we know that $\\text{LHS} = \\text{RHS}$ also holds."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.40 [3]\n",
    "\n",
    "Show that $\\lceil \\lg{(n+1)}\\rceil = \\lfloor \\lg{n} \\rfloor + 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "First let's plug in some numbers.\n",
    "\n",
    "$n=1$: $\\lceil \\lg{2}\\rceil = \\lceil 1 \\rceil = 1$ and $\\lfloor \\lg{1} \\rfloor + 1 = \\lfloor0 \\rfloor + 1 = 1$.  \n",
    "$n=2$: $\\lceil \\lg{3}\\rceil = 2$ and $\\lfloor \\lg{2} \\rfloor + 1 = 1 + 1 = 2$.  \n",
    "$n=3$: $\\lceil \\lg{4}\\rceil = 2$ and $\\lfloor \\lg{3} \\rfloor + 1 =1 + 1 = 1$.\n",
    "\n",
    "$n \\in \\mathbb{N}^+$.\n",
    "\n",
    "There are 3 cases for $n$: $n$ is a power of 2, $n+1$ is a power of 2, or neither $n$ nor $n+1$ is a power of 2. The only overlap between these cases is $n=1$, and we showed above that the equation is true for $n=1$.\n",
    "\n",
    "**Case 1:** Suppose that $n$ is a power of 2. Then there exists a positive integer $m$ such that $n = 2^m$. Furthermore, we can assume that $n+1$ is not a power of 2, otherwise $n=1$ which we already showed verified the equation.\n",
    "\n",
    "$\\text{RHS} = \\lfloor \\lg 2^m\\rfloor + 1 = \\lfloor m\\rfloor + 1 = m+1$\n",
    "\n",
    "Now because for $m>1$ the difference between $2^m$ and $n^{m+1}$ is greater than 1, we know that $n+1$ lies between $2^m$ and $2^{m+1}$, and therefore $\\lg{(n+1)}$ lies between $\\lg{2^m} = m$ and $\\lg{2^{m+1}} = m+1$. We can then write\n",
    "\n",
    "$\\text{LHS} = \\lceil \\lg{(n+1)}\\rceil = m+1$.\n",
    "\n",
    "Therefore for this case the equation holds.\n",
    "\n",
    "**Case 2:**  Suppose that $n+1$ is a power of two. Again, we also assume that $n>1$; the equation has already been shown to hold for $n=1$.\n",
    "\n",
    "There exists a positive integer $m$ such that $n+1 = 2^m$. Since $n\\neq 1$ and the difference between adjacent powers of 2 is greater than 1 for powers greater than 1, we know that $n$ lies between $2^{m-1}$ and $2^m$, and therefore $\\lg{n}$ lies between $m-1$ and $m$. We can then write\n",
    "\n",
    "$\\text{LHS} = \\lceil \\lg{(n+1)}\\rceil = \\lceil \\lg{2^m}\\rceil = m$\n",
    "\n",
    "$\\text{RHS} = \\lfloor \\lg n\\rfloor + 1 = (m-1) + 1 = m$\n",
    "\n",
    "Since both sides equal $m$, the equation holds in the case.\n",
    "\n",
    "**Case 3:** Suppose that $n>1$ and that neither $n$ nor $n+1$ are a power of 2.\n",
    "\n",
    "Since for $n>1$ the distance between adjacent powers of 2 is greater than 1, we know that both $n$ and $n+1$ lie between $2^m$ and $2^{m+1}$ for some $m\\geq1$, and therefore that $\\lg n$ and $\\lg{(n+1)}$ lie between $m$ and $m+1$. We can then write\n",
    "\n",
    "$\\text{LHS} = \\lceil \\lg{(n+1)}\\rceil = m+1$\n",
    "\n",
    "$\\text{RHS} = \\lfloor \\lg n\\rfloor + 1 = (m) + 1 = m+1$\n",
    "\n",
    "Since both sides are equal, the equation holds for this case.\n",
    "\n",
    "Because the equation holds for all cases, it holds for all $n>0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.43 [5]\n",
    "\n",
    "You are given a set $S$ of $n$ numbers. You must pick a subset $S'$ of $k$ numbers from $S$ such that the probability of each element of $S$ occurring in $S'$ is equal (i.e., each is selected with probability $k\\,/\\,n$). You may make only one pass over the numbers. What if $n$ is unknown?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "First we address the case where $n$ is known.\n",
    "\n",
    "The problem imposes 2 constraints: 1) that the probability of each number in $S$ appearing in $S'$ be the same, and 2) that we select exactly $k$ numbers.\n",
    "\n",
    "My first thought is to iterate over the numbers in $S$, and for each number, choose to include it in $S'$ with probability $k\\,/\\,n$. One can imagine having a weighted coin where you can set the probability of heads arbitrarily, and flipping it with $p = k \\, / \\, n$ for each element of $S$. The problem with this procedure is that there is a non-zero probability of selecting 0 elements, all $n$ of the elements, or any number in between. Actually, the probability of $m$ numbers being included in $S'$ will form a binomial distribution. Yes, the mode and mean (expected value) will be $k$, but we are required to select exactly $k$, not just in the average case.\n",
    "\n",
    "My second though is to generate the set of all $n$ choose $k$ subsets of size $k$ containing numbers from $1$ through $n$ and pick one subset at random. But let's say that such an algorithm is not available to us.\n",
    "\n",
    "To enforce that we select exactly $k$ numbers, we can modify the probability of selection as we go. For example, if we have already included $k$ numbers, we set $\\text{P(selection)} = 0$ for all remaining elements of $S$. Actually, we are *conditioning* the selection probabilities on the outcomes of previous selections.\n",
    "\n",
    "Let's take an example. Let $S = \\{1, 2, 3\\}$ and let $k=1$. First we consider selecting number $1$. This element needs to have a selection probability of $1\\,/\\,3$, and since there are no previous decisions to condition on, we must set $P(1) = 1 \\, / \\, 3$. Now consider number 2. We must condition its selection probability on whether or not number 1 was included. Written out, $P(2) = P(2|1)\\cdot P(1) + P(2|\\bar{1})\\cdot P(\\bar{1})$, where $\\bar{1}$ indicates that number 1 was not selected. If number 1 was selected, then $P(2|1)= 0$, since we are only allowed to select 1 number. Therefore we have $P(2) = P(2|\\bar{1})\\cdot P(\\bar{1})$, meaning the only way for the number 2 to be selected is for number 1 to be NOT selected, and then for number 2 to be selected. This probability must come out to $1\\, / \\, 3$. Plugging in $P(\\bar{1}) = 1 - P(1) = 2 \\, / \\, 3$, we have $P(2) = P(2|\\bar{1})\\cdot 2 \\, / 3 = 1 \\,/ \\, 3$. Therefore $P(2|\\bar{1}) = 1 \\, / \\, 2$. Now consider number 3. If either numbers 1 or 2 have already been included, then $P(3) = 0$, otherwise $P(3) = 1$. Does this come out to an overall selection probability of $1 \\, / \\, 3$? The only way number 3 can be selected is for both numbers 1 and 2 to be NOT selected. The probability of this happening is $P(3) = P(\\bar{1}) \\cdot P(\\bar{2}|\\bar{1})$ $= (1 - P(1)) \\cdot (1 - P(2|\\bar{1}))$ $= (2 \\, / 3) \\cdot (1 \\, / \\, 2)$ $= 1 \\, / \\, 3$.\n",
    "\n",
    "In conditioning selection probabilities in this way, we have enforced the 2 desired constraints.\n",
    "\n",
    "Let's take one more example before we try to generalize to arbitrary $n$ and $k$. Let $S = \\{ 1, 2, 3\\}$ and $k = 2$. Every element must have a selection probability of $P = 2 \\, / \\, 3$. To enforce this on number 1, we set $P(1) = 2 \\, / \\, 3$. Now consider number 2. The general form of its selection probability is $P(2) = P(2|1) \\cdot P(1) + P(2|\\bar{1}) \\cdot P(\\bar{1})$. Plugging in the probabilities for number 1, we have $P(2) = P(2|1) \\cdot 2 \\, / \\, 3 + P(2|\\bar{1}) \\cdot 1 \\, / \\, 3$. If number 1 was NOT selected, since there are only 2 numbers remaining and $k = 2$, we must select number 2. Therefore $P(2|\\bar{1}) = 1$, leaving us with $P(2) = P(2|1) \\cdot 2 \\, / \\, 3 + 1 \\, / \\, 3$. Since this must equal $2 \\, / \\, 3$, we must have $P(2|1) = 1 \\, /\\,2$. Now consider number 3. If both numbers 1 and 2 were selected, then $P(3) = 0$. Otherwise, $P(3) = 1$. Does this produce an overall selection probability of $P(3) = 2 \\, / \\, 3$? The only way for 3 to be NOT selected is for both numbers 1 and 2 to be selected. This will occur with probability $P(1) \\cdot P(2|1) = 2 \\, / \\, 3 \\cdot 1 \\, / \\, 2 = 1 \\, / \\, 3$. Therefore $P(\\bar{3}) = 1 \\, / \\, 3$ and $P(3) = 1 - 1 \\, / \\, 3 = 2 \\, / \\, 3$.\n",
    "\n",
    "We successfully enforced both constraints.\n",
    "\n",
    "To generalize this to arbitrary $n$ and $k$, let's look at the selection of number 2 in the previous example. We will write $k'$ for the number of unassignmed \"slots\" remaining in $S'$, and $n'$ for the number of numbers in $S$ which have yet to be considered. If number 1 had already been selected, then we have $k' = 1$ and $n' = 2$; we are choosing whether number 2 or 3 should fill the remaining vacancy in $S'$. We calculated in this case that $P(2|1) = 1 \\, /\\,2$. In the event that number 1 was NOT selected, we have $k'=2$ and $n'= 2$. So both numbers 2 and 3 must be selected to fill the 2 vacancies in $S'$. Therefore $P(2|\\bar{1}) = 1$. In both these cases, $P(2) = k' \\, / \\, n'$. Indeed, this equation holds for numbers 1 and 3 as well. Regarding number 1, $k' = k$ and $n' = n$, and so we set $P(1) = k \\, / \\, n$. Regarding number 3, since this number was last, we had $n' = 1$ and $k'$ equal to either $0$ or $1$, resulting in selection probabilities of $0 \\, / \\, 1$ or $1 \\, / \\, 1$.\n",
    "\n",
    "This suggests that as we iterate over $S$, we keep track of the remaining number of vacancies in $S'$ as $k'$, and the remaining number of elements from $S$ to be considered as $n$, and for each number in $S$, include it in $S'$ with probability $k' / n'$. The two examples above suggests that this procedure works in general.\n",
    "\n",
    "To prove that this does in fact hold, suppose that we have already considered $\\bar{n}$ numbers and we are now considering including number $\\bar{n}+1$. We would have to show that\n",
    "\n",
    "$$ P(\\bar{n} + 1) = \\sum_{\\bar{k} = 0}^{\\bar{n}} P(\\bar{n} + 1|\\bar{k}) \\cdot F(\\bar{k}, \\bar{n}) = \\sum_{\\bar{k} = 0}^{\\bar{n}} \\frac{k'}{n'} \\cdot F(\\bar{k}, \\bar{n}) = \\sum_{\\bar{k} = 0}^{\\bar{n}} \\frac{k - \\bar{k}}{n - \\bar{n}} \\cdot F(\\bar{k}, \\bar{n}) \\stackrel{WTS}{=} \\frac{k}{n}$$\n",
    "\n",
    "where we have set $\\bar{n} = n - n'$ (the number of numbers preceding number $\\bar{n} + 1$), $\\bar{k} = k - k'$ (how many numbers were selected from those before number $\\bar{n} + 1$), and $F(\\bar{k}, \\bar{n})$ (the probability that exactly $\\bar{k}$ numbers were selected amongst the previous $\\bar{n}$).\n",
    "\n",
    "Since amongst the first $\\bar{n}$ numbers, each one has an equal probability of $k \\, / \\, n$ of being selected, the probability that exactly $\\bar{k}$ are included is the same as the probability of obtaining exactly $\\bar{k}$ heads while flipping a coin $\\bar{n}$ times that has a probability of heads of $p = k \\, / \\, n$. This is given by $(P_{heads})^{H}   \\cdot (P_{tails})^{N-H} \\cdot \\binom{N}{H})$ where $H$ is the number of heads and $N$ is the total number of flips. Plugging this in for $F(\\bar{k}, \\bar{n})$ we have:\n",
    "\n",
    "$$\n",
    "\\sum_{\\bar{k} = 0}^{\\bar{n}} \\frac{k - \\bar{k}}{n - \\bar{n}} \\cdot F(\\bar{k}, \\bar{n})\n",
    "= \\sum_{\\bar{k} = 0}^{\\bar{n}} \\frac{k - \\bar{k}}{n - \\bar{n}} \\cdot \\left(\\frac{k}{n}\\right)^{\\bar{k}} \\cdot \\left(\\frac{n-k}{n}\\right)^{\\bar{n} - \\bar{k}} \\cdot \\binom{\\bar{n}}{\\bar{k}}\n",
    "\\stackrel{WTS}{=} \\frac{k}{n}\n",
    "$$\n",
    "\n",
    "[Upon reviewing this problem, I realize that this assumes that the outcomes of coin tosses are independent, which is contrary to our practice of conditioning later selections on earlier ones. But mysteriously, it still comes out right. I am not yet sure why.]\n",
    "\n",
    "Rather than show that this is correct by hand, I did two things. One, I plugged this into Wolfram Alpha and indeed it holds. Below is the screenshot, where $x = \\bar{k}$ and $m = \\bar{n}$. Visually, the $n-m$ should be under the $k-x$.\n",
    "\n",
    "![Hallock_Fig_2-1.png](Figures/Hallock_Fig_2-1.png)\n",
    "\n",
    "\n",
    "**Second, I found another way of thinking about the problem.** The problem asks us to iterate over the numbers and select whether each number is to be included in $S'$. A *probabilistically equivalent* way of thinking about the problem is to imagine that the numbers which are included in $S'$ *are already set*, and we sequentially \"*reveal*\" whether each one is indeed included. Since we have no prior information, number 1 is included with probability $k\\,/\\,n$. Once we \"*reveal*\" whether number 1 is included, we update our information about the other $n-1$ numbers, namely that they each have an equal chance of being found amongst the $k$ or $k-1$ remaining vacancies in $S'$. This formulation makes it apparent why the probability that each number is included is $k' \\, / \\, n'$. The math above shows that these two formulations are indeed the same.\n",
    "\n",
    "**If $n$ is unknown**, we cannot guarantee both constraints, that every number has an equal chance of being included, and that exactly $k$ are included. The best we can do is pick a surrogate $n$ based on the relative importance of giving every number an equal chance of inclusion (pick a high $n$, resulting in a low probability of inclusion) versus including exactly $k$ numbers (pick a low $n$, resulting in a high probability of inclusion, but once we select $k$ we have no more room in $S'$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.46 [5]\n",
    "\n",
    "You have a 100-story building and a couple of marbles. You must identify the lowest floor for which a marble will break if you drop it from this floor. How fast can you find this floor if you are given an infinite supply of marbles? What if you have only two marbles?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "If we have an infinite number of marbles, we can do a binary search. Drop a marble from floor 50, and if it breaks, try floor 25. If it doesn't, try floor 75. And repeat. This will take $\\lceil \\lg 100 \\rceil = 7$ marbles. However, if a marble doesn't break, we can reuse it. On average, half of the drops will break the marble, and half won't. Therefore, the number of marbles is $\\lceil 7 \\, / \\, 2\\rceil = 4$. When the lowest floor is identified that breaks the marbles, if this was discovered with a reused marble, then there is a chance that the marble only broke because it was weakened from a previous drop. Therefore a new marble should be dropped from this floor to make sure that new marbles will break.\n",
    "\n",
    "If we only have 2 marbles, then we can leverage the fact that we can reuse marbles. We drop the first marble from floor 1, then floor 2, then floor 3, and so on until we find the first floor for which it breaks. Then we drop the second marble from that floor to be sure that it can break new marbles. If the new marble doesn't break, we keep dropping it from higher floors until we find the one that breaks the newer marble. If floor $n$ is the lowest breakable floor, this procedure will take $n + 1$ drops including the double check, 51 drops on average.\n",
    "\n",
    "If we assume that marbles do not become more brittle when they survive drops, which may be a fair assumption, then we can drop the first marble from just the odd-numbered floors, that is, from floor 1, then 3, then 5... If floor $n$ is the floor that breaks the marble, then either floor $n$ or $n - 1$ is the lowest such floor. Drop marble 2 from floor $n-1$ to find out which. This procedure will take $\\lceil (n+1) \\, / \\, 2 \\rceil + 1$ drops, 27 drops on average. For example, if $n = 9$, then we drop from floors 1, 3, 5, 7, 9, and then floor 8. This is a total of 6, which is equal to $\\lceil (9+1) \\, / \\, 2 \\rceil + 1 = 5 + 1 = 6$. If $n = 10$, then we drop from floors 1, 3, 5, 7, 9, 11, and then floor 10. This is a total of 7, which is equal to $\\lceil (10+1) \\, / \\, 2 \\rceil + 1 = 6 + 1 = 7$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}