Chapter_04_Divide_and_Conquer/exercises_4.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.4 The recursion-tree method for solving recurrences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-1\n",
    "\n",
    "> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=3T(\\left \\lfloor n / 2 \\right \\rfloor) + n$. Use the substitution method to verify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{\\lg n - 1}(\\frac{3}{2})^i n + \\Theta(n^{\\lg 3}) \\\\\n",
    "& = & \\displaystyle \\frac{(3/2)^{\\lg n}-1}{(3/2)-1}n + \\Theta(n^{\\lg 3}) \\\\\n",
    "& = & \\displaystyle 2n^{\\lg 3} - 2n + \\Theta({n^{\\lg 3}}) \\\\\n",
    "& = & \\displaystyle \\Theta({n^{\\lg 3}})\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-2\n",
    "\n",
    "> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n/2)+n^2$. Use the substitution method to verify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{\\lg n - 1}(\\frac{1}{2})^i n^2 + \\Theta(1) \\\\\n",
    "& = & \\displaystyle \\frac{(1/2)^{\\lg n}-1}{(1/2)-1}n^2 + \\Theta(1) \\\\\n",
    "& = & \\displaystyle 2n^2 - \\frac{2}{n} + \\Theta(1) \\\\\n",
    "& = & \\displaystyle \\Theta(n^2) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-3\n",
    "\n",
    "> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=4T(n/2+2)+n$. Use the substitution method to verify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{\\lg n - 1}(2^in) + \\sum_{i=0}^{\\lg n - 1}(2^{2i+1}) + \\Theta(n^2) \\\\\n",
    "& = & \\displaystyle \\frac{2^{\\lg n}-1}{2-1}n + \\Theta(n^2) \\\\\n",
    "& = & \\displaystyle n^2 - n + \\Theta(n^2) \\\\\n",
    "& = & \\displaystyle \\Theta(n^2) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-4\n",
    "\n",
    "> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=2T(n-1)+1$. Use the substitution method to verify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{n - 1}(2^i) + \\Theta(2^n) \\\\\n",
    "& = & \\displaystyle \\frac{2^n-1}{2-1} + \\Theta(2^n) \\\\\n",
    "& = & \\displaystyle 2^n - 1 + \\Theta(2^n) \\\\\n",
    "& = & \\displaystyle \\Theta(2^n) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-5\n",
    "\n",
    "> Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=T(n-1)+T(n/2)+n$. Use the substitution method to verify your answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(n^{\\lg n})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-6\n",
    "\n",
    "> Argue that the solution to the recurrence $T(n)=T(n/3)+T(2n/3)+cn$, where $c$ is a constant, is $\\Omega(n \\lg n)$ by appealing to a recursion tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Shortest path is $\\log_3n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-7\n",
    "\n",
    "> Draw the recursion tree for $T(n)=4T(\\left \\lfloor n / 2 \\rfloor \\right) + cn$, where $c$ is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Theta(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-8\n",
    "\n",
    "> Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) = T(n-a) + T(a) + cn$, where $a \\ge 1$ and $c > 0 $ are constants."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{n/a}(c(n-ai) )+ cn \\\\\n",
    "& = & \\displaystyle \\Theta(n^2) \\\\\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4-9\n",
    "\n",
    "> Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n)=T(\\alpha n)+T((1-\\alpha)n)+cn$, where $\\alpha$ is a constant in the range $0 < \\alpha < 1$ and $c > 0$ is also a constant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{lll}\n",
    "T(n) & = & \\displaystyle \\sum_{i=0}^{\\log_{1/\\alpha}n}cn + \\Theta(n) \\\\\n",
    "& = & \\displaystyle \\Theta(n\\lg n) \\\\\n",
    "\\end{array}\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
}