02_Metodos_Matematicos_para_el_Analisis_de_Algoritmos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2 Métodos Matemáticos para el Análisis de Algoritmos\n",
    "\n",
    "Para cuantificar la eficiencia de los algoritmos, utilizamos funciones que miden, por ejemplo, cuánto tiempo demora un algoritmo en ejecutarse sobre una entrada dada, cuál es su peor caso sobre un conjunto de entradas posibles, o cuánto demora en promedio, suponiendo una cierta distribución de probabilidad de las entradas. Ocasionalmente, estudiaremos el uso de otro tipo de recursos, como por ejemplo la cantidad de memoria utilizada.\n",
    "\n",
    "Es habitual que los resultados que obtengamos dependan de un parámetro $n$, que representa el tamaño del problema (por ejemplo, el número de elementos a ordenar, el número de elementos en un conjunto en el que hay que hacer una búsqueda, etc.). Por lo tanto, nuestras funciones serán normalmente *funciones discretas*, esto es funciones cuyo argumento es un número entero nonegativo. Como notación, para este tipo de funciones utilizaremos indistintamente una notación de funciones $f(n)$ o de sucesiones $f_n$.\n",
    "\n",
    "Tal como en Física el estudio de funciones de variable continua $f(t)$ conduce a ecuaciones diferenciales que luego hay que resolver, acá el estudio de funciones de variable discreta $f(n)$ conducirá a *ecuaciones de recurrencia*, y en este capítulo veremos algunos métodos para resolver ese tipo de ecuaciones."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notación $O$\n",
    "\n",
    "Al trabajar con funciones que pueden ser muy complicadas, en la práctica resulta útil poder ignorar los términos de orden inferior para concentrarse en el que determina la forma en que la función evoluciona cuando $n \\rightarrow \\infty$. También resulta útil en ese caso poder ignorar factores constantes, para concentrarse en la forma como la función depende de $n$.\n",
    "\n",
    "Utilizaremos la notación\n",
    "$$\n",
    "f(n)=O(g(n))\n",
    "$$\n",
    "si existe una constante $C$ y un número $n_0$ tal que\n",
    "\n",
    "$$\n",
    "|f(n)| \\le C|g(n)|\n",
    "$$\n",
    "\n",
    "para todo $n\\ge n_0$.\n",
    "\n",
    "Cuando la notación $O(g(n))$ aparezca en medio de una fórmula, representará a una función que cumple con la condición anterior.\n",
    "\n",
    "Es importante notar que la notación $O$ provee una cota superior, la cual puede o no ser cercana a la función de la izquierda.\n",
    "Más adelante veremos una notación más ajustada.\n",
    "\n",
    "### Ejemplos\n",
    "\n",
    "* $3n=O(n)$\n",
    "* $2=O(1)$\n",
    "* $2=O(n)$\n",
    "* $3n+2=O(n)$\n",
    "\n",
    "La notación $f(n)=O(g(n))$ es utilizada por la mayoría de los autores, pero hay que usarla con cuidado, porque la igualdad que ahí aparece **no es una relación reflexiva**.\n",
    "En efecto, de $3n=O(n)$ y $2=O(n)$, **no** podemos deducir que $3n=2$.\n",
    "Hay que tener presente siempre que lo que aparece a la derecha del signo igual contiene menos información que lo de la izquierda.\n",
    "\n",
    "Para evitar las posible confusiones que podrían derivar de este uso no estándar del signo igual, algunos autores prefieren escribir\n",
    "\n",
    "$$\n",
    "f(n) \\in O(g(n))\n",
    "$$\n",
    "\n",
    "en donde $O(g(n))$ se interpreta como el _conjunto_ de todas las funciones que acotan a $f(n)$ de la manera indicada.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notación $\\Omega$\n",
    "\n",
    "De manera análoga, se puede definir una notación de cota inferior.\n",
    "\n",
    "Diremos que\n",
    "$$\n",
    "f(n)=\\Omega(g(n))\n",
    "$$\n",
    "si existe una constante $C$ y un número $n_0$ tal que\n",
    "\n",
    "$$\n",
    "|f(n)|\\ge C|g(n)|\n",
    "$$\n",
    "\n",
    "para todo $n\\ge n_0$.\n",
    "\n",
    "### Ejemplos\n",
    "\n",
    "* $3=\\Omega(1)$\n",
    "* $3n=\\Omega(n)$\n",
    "* $3n=\\Omega(1)$\n",
    "* $3n+2=\\Omega(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notación $\\Theta$\n",
    "\n",
    "La notación $\\Theta$ nos permite especificar el orden exacto de crecimiento de una función.\n",
    "\n",
    "Diremos que\n",
    "$$\n",
    "f(n)=\\Theta(g(n))\n",
    "$$\n",
    "si $f(n)=O(g(n))$ y $f(n)=\\Omega(g(n))$\n",
    "\n",
    "### Ejemplo\n",
    "\n",
    "* $3n+2=\\Theta(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Esta notación enfatiza que lo más importante, cuando $n$ crece, es el orden de magnitud de las funciones, y que podemos ignorar constantes multiplicativas y términos de orden inferior para comparar funciones a largo plazo.\n",
    "\n",
    "Por otra parte, si por alguna razón queremos comparar funciones para $n$ pequeño, ahí toda la información es significativa, y como muestra el siguiente gráfico, en ese rango una solución \"ineficiente\" puede resultar preferible a otra que solo es eficiente para $n$ grande:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/d3fzzAAAACXBIWXMAAAsTAAALEwEAmpwYAAAplklEQVR4nO3dd3hUZdrH8e+TRhpJSIWQhIQaQhJCCIQiiIqIiiDFVdaGLovrdndXiuKKiwVdV1bdiruAvrZVQhMVFSygAgpoCiH0AKEkISG9Z573jzPUhSWEyZyZzP25rrnOmTOTOXcG8svJM+e5j9JaI4QQwvm4mV2AEEKI1pEAF0IIJyUBLoQQTkoCXAghnJQEuBBCOCkPe+4sNDRUx8bG2nOXQgjh9LZt23ZCax12/na7BnhsbCxbt2615y6FEMLpKaUOXmi7DKEIIYSTkgAXQggnJQEuhBBOyq5j4BfS2NhIQUEBdXV1ZpfiFLy9vYmKisLT09PsUoQQJjM9wAsKCujYsSOxsbEopcwux6FprSkpKaGgoIC4uDizyxFCmOySQyhKqcVKqSKlVM5523+hlMpTSu1QSj3X2gLq6uoICQmR8G4BpRQhISHy14oQAmjZGPhSYOzZG5RS1wATgP5a637A81dShIR3y8l7JYQ45ZIBrrXeAJSet/lBYIHWut76nKI2qE0IIZzeyeoGnnhvBxV1jTZ/7daehdIbGKGU2qKU+kIpNehiT1RKzVBKbVVKbS0uLm7l7oQQwrlorXk/6xjXL/yC/9t0kG/2n38cfOVa+yGmBxAMDAEGAe8opbrrC1wdQmu9CFgEkJaWJlePEEK0e4UVdTy2MoePcwtJjgrk/36UTt8uATbfT2uPwAuA5drwDWABQm1XlvMqKytjypQpxMfH07dvXzZt2mR2SUIIO9Fa859vDzH6hS/4Yncxj9wUz/IHh7VJeEPrA3wlcA2AUqo34AWcsFFNDu3zzz9n2rRpF338V7/6FWPHjiUvL4/MzEz69u1rv+KEEKY5VFLDXf/ewqyMbBK6BPDRr0cyY2QPPNzbbr7kJYdQlFJvAaOAUKVUAfA4sBhYbD21sAG490LDJ85k0qRJJCQksGHDBvLz81m8eDGjR4++rNcoLy9nw4YNLF26FAAvLy+8vLzaoFohhKNotmiWfp3P8x/twt1N8dTERKYOisHNre3PGLtkgGutp17kobtsXAtPvLeD3KMVNn3NhMgAHr+l3yWfl52dzbBhw9iwYQMrVqzgjTfeuOwAP3DgAGFhYdx3331kZmYycOBAXnzxRfz8/FpbvhDCge0urGTmsiy+P1zGtfHhPDUxkS6BPnbbv/RCAWpqaigvL+ehhx4CjOn9QUFB5zwnPT2dlJQUpk+fzurVq0lJSSElJYWPPvro9HOamprYvn07Dz74IN999x1+fn4sWLDAnt+KEMIOGposvLR+Dze/tJGDJdW8eEcK/743za7hDQ4wlf5sLTlSbgu5ubkMHDgQd3d3ALKyskhMTDznOVu2bAGMMfClS5eeHiY5W1RUFFFRUaSnpwMwZcoUCXAh2pmsgjJmLssi73glt/SPZN4tCYT4dzClFjkCxxg+SUlJOX0/KyuL5OTky36dzp07Ex0dza5duwBYv349CQkJtipTCGGi2oZmnvlgJ7f+9StO1jTwyj1pvDx1gGnhDQ52BG6W7Ozs00fNADk5Of91BN5SL7/8MnfeeScNDQ10796dJUuW2KpMIYRJNu8vYXZGFvklNUwdHMOcm+IJ8Da/I6iy58kjaWlp+vxLqu3cuVNOtbtM8p4JYR+VdY0s+DCPN7YcoluIL89MSmJYD/tPeVFKbdNap52/XY7AhRDiAj7NK+TRFTkUVtTx4xFx/Ob6Pvh4uZtd1jkkwIUQ4iwlVfX8YU0uq74/Su8If/5+13BSooPMLuuCJMCFEAJjGvx7WceYt3oHlXWN/Hp0L346qideHo57rocEuBDC5R0rr+WxlTms21lE/+ggnpucTJ/OHc0u65IkwIUQLsti0bz97WGe+WAnjRYLc2/uy33D43C3wzR4W5AAF0K4pPwT1cxensXm/aUM7R7CgslJdAtxrrYXEuBCCJfSbNEs/vIAf/pkF55ubiyYlMTtg6Kd8nKFEuBCCJex63glM5dlkllQzui+4Tx5axKdA73NLqvVHPfjVTvz9/c3uwQWLlxIv379SExMZOrUqXL1eSFspKHJwsJPdjPu5Y0UnKzl5akDeOWeNKcOb5AAt6v/dTGII0eO8NJLL7F161ZycnJobm7m7bfftm+BQrRD3x8uY9zLG3lx/R7GJUfyyW+u5pb+kU45ZHI+CfDzvPDCCyQmJpKYmMif//zn09vnz59Pnz59uOqqq5g6dSrPP//86ccmTZrE3LlzGTlyJDExMaxbt65V+25qaqK2tpampiZqamqIjIy80m9HCJdV29DMk2tymfS3r6isa2LxtDQW3p5CsF/7uciKY42Bfzgbjmfb9jU7J8GNLWvpum3bNpYsWcKWLVvQWpOens7VV19NU1MTGRkZZGZm0tjYSGpqKgMHDjz9dba4GETXrl353e9+R0xMDD4+PowZM4YxY8Zc1msIIQxf7zvB7IxsDpXWcNeQGGaNjaejAzSfsjXHCnCTffnll0ycOPH0FXQmTZrExo0bsVgsTJgwAW9vb7y9vbnllltOf01LLwZRX19PVVUVpaWlp1vXPvvss9xwww0AnDx5klWrVnHgwAGCgoK47bbbeP3117nrLptf+EiIdquirpFnPtjJW98cJjbEl7dnDGFI9xCzy2ozjhXgLTxSdiS2uhjEunXriIuLIywsDDB+eXz99dcS4EK00LrcQh5dmU1xZT0PXN2dh0b3xtvTsZpP2ZqMgZ9lxIgRrFy5kpqaGqqrq1mxYgUjRoxg+PDhvPfee9TV1VFVVcWaNWtOf42tLgYRExPD5s2bqampQWvN+vXrpWWsEC1QUlXPL976jumvbaWTrxcrfzacOTf2bffhDY52BG6y1NRUpk2bxuDBgwGYPn06AwYMAGD8+PEkJycTERFBUlISgYGBgO0uBpGens6UKVNITU3Fw8ODAQMGMGPGDBt8V0K0T1prVmceZd7qHVTXN/Pb63vzwNU9HLr5lK3JBR1aqKqqCn9/f2pqahg5ciSLFi0iNTXVlFqc5T0Toq0cLatl7socPs0rYkCM0XyqV4TjN59qLbmgwxWaMWMGubm51NXVce+995oW3kK4MotF8+Y3h1jwYR7NFs3vxyVw77BYp2k+ZWsS4C305ptvml2CEC7twIlqZmVk8c2BUob3DOGZicnEhPiaXZapJMCFEA6tqdnCv748wMJPduPl4cZzk5O5LS2qXcykvFIS4EIIh5V7tIJZGVlkHylnTEIE829NJCLAufuX2JJDBLjWWn6btpA9P3QWwiz1Tc385dO9/P3zfQT5evLXH6ZyU1JnyYnzmB7g3t7elJSUEBISIv84l6C1pqSkBG9vOQIR7de2gyeZlZHF3qIqJqV25bGbE+jUjvqX2JLpAR4VFUVBQQHFxcVml+IUvL29iYqKMrsMIWyuur6J5z/exdKv84kM9GHpfYMY1Sfc7LIcmukB7unpSVxcnNllCCFMtHFPMXOWZ1NwspZ7hnZj5th4/DuYHk8OT94hIYRpymsaeeqDXN7ZWkD3UD/eeWAog+OCzS7LaUiACyFMsTbnOI+tyqG0uoGfjurBL6/r5RL9S2xJAlwIYVfFlfXMW72D97OPkdAlgCXTBpHYNdDsspySBLgQwi601izffoQ/rMmltrGZh2/ow4yR3fF0d53mU7YmAS6EaHMFJ2t4dEUOX+wuZmC3Tjw7OZme4eZfSNzZXTLAlVKLgXFAkdY68bzHfgs8D4RprU+0TYlCCGdlsWhe33KQZz/MQwPzbkngnqGxuLlo8ylba8kR+FLgL8BrZ29USkUDY4BDti9LCOHs9hVXMTsji2/zTzKiVyhPT0wiOti1m0/Z2iUDXGu9QSkVe4GHFgIzgVW2LkoI4bwamy0s2rCfF9fvwcfTnedv68/k1K4y07oNtGoMXCk1ATiitc681D+KUmoGMAOMy4YJIdqvnCPlzMrIYsfRCm5M7MwTE/oR3lFaP7SVyw5wpZQv8AjG8Mklaa0XAYvAuCLP5e5PCOH46hqbeWn9Hv65YT+dfL34+52p3JjUxeyy2r3WHIH3AOKAU0ffUcB2pdRgrfVxWxYnhHB8W/NLmZmRxf7iaianRvHYuL4E+UrzKXu47ADXWmcDpzvMKKXygTQ5C0UI11JV38Qf1+bx2uaDRAb68Nr9gxnZO8zsslxKS04jfAsYBYQqpQqAx7XW/27rwoQQjuuL3cU8sjybo+W13Ds0lodv6IOfNJ+yu5achTL1Eo/H2qwaIYRDK6tpYP6anWRsL6BHmB/vPjCUtFhpPmUW+ZUphGiRD7OP8diqHZysaeDn1/Tk59f2lOZTJpMAF0L8T0UVdfx+1Q7W7jhOv8gAXr1/EP0ipfmUI5AAF0JckNaad7cV8OSaXOqaLMwc24cZI7rjIc2nHIYEuBDivxwureGRFdls3HOCQbGdWDA5mR5h0nzK0UiACyFOa7ZoXtuUzx8/2oUC5k/ox53p3aT5lIOSABdCALC3qJJZGdlsO3iSq3uH8fSkJLoG+ZhdlvgfJMCFcHGnm0+t24NvB3de+EF/Jg6Q5lPOQAJcCBeWXVDOzIwsdh6r4OakLswb34+wjh3MLku0kAS4EC6orrGZP6/bwysb9xPi58U/7x7IDf06m12WuEwS4EK4mC37S5i9PJsDJ6q5PS2aR27uS6CPp9lliVaQABfCRVTWNfLs2jxe33yI6GAf3piezvCeoWaXJa6ABLgQLuCzvCIeXZHNsYo67h8ex+9u6I2vl/z4Ozv5FxSiHSutbmD+mlxWfHeEXuH+ZDw4jNSYTmaXJWxEAlyIdkhrzfvZx3h81Q7Kaxv55XW9+Nk1PejgIc2n2hMJcCHamcKKOuauzOGT3EKSowJ5fXo6fbsEmF2WaAMS4EK0E1pr3tl6mCff30lDk4VHborn/uFx0nyqHZMAF6IdOFRSw+zlWXy9r4T0uGCenZxMbKif2WWJNiYBLoQTa7Zolnx1gOc/3oWHmxtPT0zijkHR0nzKRUiAC+GkdhdWMnNZFt8fLuPa+HCemphIl0BpPuVKJMCFcDINTRb+/vk+/vLZHvw7ePDiHSmM7x8pzadckAS4EE4k83AZszKyyDteyfj+kTx+SwIh/tJ8ylVJgAvhBGobmlm4bjf/2rif8I7e/OueNEYnRJhdljCZBLgQDm7TvhLmLM8iv6SGqYNjmHNTPAHe0nxKSIAL4bAq6hpZ8GEeb245REywL2/+OJ1hPaT5lDhDAlwIB7R+ZyGPrsihqLKOH4+I4zfX98HHS6bBi3NJgAvhQEqq6nnivVxWZx6lT0RH/nH3QFKig8wuSzgoCXAhHIDWmtWZR3nivVwq6xp5aHRvHhzVAy8PmQYvLk4CXAiTHSuvZe6KHNbnFdE/Oog/Tkmmd0RHs8sSTkACXAiTWCyat789zDMf7KTRYmHuzX25b3gc7jINXrSQBLgQJsg/Uc3s5Vls3l/KsB4hLJiUTEyIr9llCScjAS6EHTU1W1jyVT5/+mQXnm5uLJiUxO2DomUavGgVCXAh7CTveAWzlmWRWVDO6L4RPHlrIp0Dvc0uSzgxCXAh2lh9UzN//Wwff/tsL4E+nrw8dQDjkrvIUbe4YhLgQrSh7w6dZFZGFrsLq5g4oCuPjUsg2M/L7LJEOyEBLkQbqGlo4oWPd7P4qwNEBHizeFoa18ZL8ylhW5cMcKXUYmAcUKS1TrRu+yNwC9AA7APu01qXtWGdQjiNr/eeYPbybA6V1nBnegyzb4ynozSfEm2gJdO8lgJjz9v2CZCotU4GdgNzbFyXEE6nvLaR2RlZ/PBfW3BT8PaMITw1MUnCW7SZSx6Ba603KKViz9v28Vl3NwNTbFyXEE7lk9xC5q7Mpriyngeu7s5Do3vj7SnNp0TbssUY+P3Afy72oFJqBjADICYmxga7E8JxnKiqZ97qHazJOkZ85468ck8ayVFBZpclXMQVBbhS6lGgCXjjYs/RWi8CFgGkpaXpK9mfEI5Ca83K74/wxHu5VNc38Zvre/OTq6X5lLCvVge4Umoaxoeb12mtJZiFyzhSVsujK7L5fFcxA2KCeG5yMr2k+ZQwQasCXCk1FpgJXK21rrFtSUI4JotF88Y3h1jwwU4sGh6/JYF7hsZK8ylhmpacRvgWMAoIVUoVAI9jnHXSAfjEOptss9b6J21YpxCm2l9cxeyMbL7JL+WqnqE8MymJ6GBpPiXM1ZKzUKZeYPO/26AWIRxOU7OFVzYeYOG63Xh7uPHc5GRuS4uSafDCIchMTCEuIvdoBTMzMsk5UsEN/SKYPyGR8ABpPiUchwS4EOepa2zmL5/u5R9f7CPI14u/35nKjUldzC5LiP8iAS7EWbYdLGVWRjZ7i6qYnBrFY+P6EuQrzaeEY5IAFwKorm/ijx/t4tVN+UQG+rD0vkGM6hNudllC/E8S4MLlbdxTzJzl2RScrOXeod14eGw8/h3kR0M4PvlfKlxWeU0jT76fy7vbCuge5se7PxnKoNhgs8sSosUkwIVLWptznMdW5VBa3cBPR/Xgl9f1kuZTwulIgAuXUlRZx7zVO/gg+zgJXQJYMm0QiV0DzS5LiFaRABcuQWvN8u1H+MOaXGobm3n4hj7MGNkdT3dpPiWclwS4aPcKTtbwyIocNuwuZmC3Tjw7OZme4f5mlyXEFZMAF+2WxaJ5fctBnv0wDw08Mb4fdw/phps0nxLthAS4aJf2FVcxOyOLb/NPMqJXKE9PlOZTov2RABftSmOzhUUb9vPi+j34eLrz/G39mZzaVZpPiXZJAly0GzuOljNzWRY7jlZwU1Jn5o3vR3hHaT4l2i8JcOH06hqbeWn9Hv65YT/Bfl78465UxiZK8ynR/kmAC6f2bX4ps5Zlsf9ENbcNjGLuzQkE+nqaXZYQdiEBLpxSVX0Tz63N47VNB4nq5MP//WgwI3qFmV2WEHYlAS6czhe7i3lkeTZHy2uZNiyWh2/og580nxIuSP7XC6dRVtPAH9bksnz7EXqE+bHsJ0MZ2E2aTwnXJQEunMIH2cf4/aocymoa+cW1Pfn5tT3p4CHNp4RrkwAXDq2ooo7fr9rB2h3HSeoayGv3p5MQGWB2WUI4BAlw4ZC01ry7rYAn1+RS32Rh9o3xTL8qDg9pPiXEaRLgwuEcLq3hkRXZbNxzgsGxwSyYnET3MGk+JcT5JMCFw2i2aF7blM9za3fhpmD+rYncOThGmk8JcRES4MIh7C2qZOayLLYfKmNUnzCemphE1yAfs8sSwqFJgAtTNTZb+OcX+3hp/V78Oriz8Pb+3JoizaeEaAkJcGGa7IJyHl6WSd7xSsYld2He+H6E+ncwuywhnIYEuLC7usZmFn6ym1c27ifUvwOL7h7ImH6dzS5LCKcjAS7sasv+EmYvz+bAiWruGBTNnJv6EugjzaeEaA0JcGEXlXWNPLs2j9c3HyIm2Jc3p6czrGeo2WUJ4dQkwEWb+yyviEdXZHOsoo4fXRXHb8f0xtdL/uuJdkhraKiGunKoK4PasjPLHtdCgG371MtPkWgzpdUNzF+Ty4rvjtAr3J+MB4eRGtPJ7LKEuLTGWiN0a08at1MhfLH108tysDRe+DV/+K4EuHB8Wmvezz7G46t2UF7byK+u68VPr+khzaeEfZ06Gq49CbWlZ8L4v25l/72tqe7ir6vcwDsQvIPAJ8hYBkWfe/+cpfW5HW1/lSgJcGFThRV1zF2Zwye5hfSPCuSNH6cT31maT4kr1Nx0JohrSq3LkrPWrQF9ankqsJsbLv6aHj7g08kIWZ9gCO5uvd/prO2drEHc6UwodwgAN8foySMBLmxCa81/vj3MUx/spLHZwtyb+3Lf8DjcZRq8OJ+l2Rq2JRe4lZ63tK7Xl1/89dy9jAD2DTaWIT3Ad5Cx7tPJuv1UKAefCWNP55/pe8kAV0otBsYBRVrrROu2YOA/QCyQD/xAa32y7coUjuxgSTVzlmfz9b4S0uOCeXZyMrGhfmaXJeylsQ5qTkD1Ceuy5Kz71hA+e732JKAv/FqevuAbYoSubwh0ij1z/1RIn73uEwxefuCiM3dbcgS+FPgL8NpZ22YD67XWC5RSs633Z9m+POHImi2aJV8d4PmPd+Hh5sbTE5O4Y1C0NJ9yds2NRuBWF1tv1vWaU9tKzrp/AhqqLvw6yt0IX79QYxnR79z7p4M69Exgt4OjYnu6ZIBrrTcopWLP2zwBGGVdfxX4HAlwl7K70Gg+9f3hMq6ND+epiYl0CZQfPofVUAPVRVBlvZ0K57PXT91qL/LHtJsH+IUZAewXZowZnwpjv1AjiE8vQ4zxYhc9MraX1o6BR2itj1nXjwMRF3uiUmoGMAMgJiamlbsTjqKhycLfP9/HXz7bg38HD168I4Xx/SOl+ZQZmhqsoVxoDeazl4XnhvXFjpK9A8Ev3Ajk8L7gd/W5IX32unegBLKDueIPMbXWWil1kQEt0FovAhYBpKWlXfR5wvFlHi5j5rIsdhVWMiElkt+PSyBEmk/ZXn0lVBZC1XGoPG6EceVxayBbl5XHjTMtLsSnkxHK/uHQNdW6HmZdRpxZ9wsFD/n3c2atDfBCpVQXrfUxpVQXoMiWRQnHUtvQzAuf7OLfXx4gvKM3/7onjdEJF/2jS1xMYy1UHjPCt+KoNZStIV15/MxjFzpadu9ghG/HCGPoImbomft+4cbSP8I4UpZQdhmtDfDVwL3AAutylc0qEg7l630nmLM8m4MlNfwwPYbZN8YT4C3Np86htTFuXHEEKo4Zy8pjZ+5XWm8XGlv28IaOnY1JHhGJ0HP0mfv+Eca6f4RxVC3DF+I8LTmN8C2MDyxDlVIFwOMYwf2OUupHwEHgB21ZpLC/irpGnvkgj7e+OUS3EF/e+vEQhvYIMbss+zsVzuUFRiCXFxhHzxVHrQF9xFj/r5l7ygjegC7QKc44Yg7oAh0jrcsuRjjLB33iCrTkLJSpF3noOhvXIhzEutxCHl2ZTXFlPTNGdueh0b3x8Wqn0+Ab66zBfNgI5/KCs9atAd1Yc+7XuHkYARzQFbqkQJ+bjPWAyDM3/whwl79URNuSmZjitJKqep54L5fVmUeJ79yRRXen0T86yOyyrkx9JZQdst4OQ/mp5WFjWX3+xzfWI+fAKIhIgF5jILCrcT8gylj3CwO3dvoLTTgVCXCB1prVmUeZt3oHVfVNPDS6Nw+O6oGXh2P0e/ifGmvh5EEoO3hmWXbozPL8cWf3DkbjocBo6DMWAmOMcA6MMrZ3jAQPL3O+FyEukwS4iztWXsvcFTmszysiJTqI56Yk0zuio9llnaG1cRpd6QE4eQBO5p91O2icxXE2D28IijFuXdPOrAfFGKHtF+YwjYiEuFIS4C7KYtG8/e1hnvlgJ40Wk5tPWSxQUQCl+41byb5zA/ucMWhlHC13ijXO2OgUa711g6BuxrnP8qGgcBES4C4o/0Q1s5dnsXl/KcN6hLBgUjIxIb5tu1OtjXOcS/dByV7rbZ9xO5kPzfVnnuvhbZy5ERwH3a8xAjo4ztgWFCNDHEJYSYC7kKZmC4u/OsCfPt6Nl7sbCyYlcfugaNtOg2+osYbzHjhhvZXsMYL67Akq7h2MCSmhvaD3DUYL0ODuENzDOMNDhjmEuCQJcBeRd7yCWcuyyCwoZ3TfCJ68NZHOgd6tf8GaUijeBSd2GcviXXBit3F2x2nKOGIO7WWcBx3S0wjqkJ7GGR0S0kJcEQnwdq6+qZm/fraPv322l0AfT16eOoBxyV1aftRdUwrFeVC089xldfGZ53j4WEN6CITeC6E9IbS3cUQt7UGFaDMS4O3Yd4dOMisji92FVUwc0JXHxiUQ7HeR8ePGOuNoujAXCnOgKNdYP/ssDy9/CIs3hjzC4iG0D4T1Mc7ukKNpIexOArwdqmlo4k8f72bxVwfoHODNkmmDuCY+/MwTKguhMBuOn7rlGOPWutl43L2DEcw9rjFajIb1NZaBUXKGhxAORAK8nflq7wlmL8/icGktd6VHM3uIN/6lX8En358J7LNnHwbFGE2UEsYbV0wJ72cMfbjLfw0hHJ38lLYT5TUN/HPleg7nfMnP/Aq4MbaQwLxcyLReDNbNE8Ljodf10DnJuEUkGhd3FUI4JQlwZ1VZCEe2wdHtnNi1Cc/C75lJFXiBtnRAufWDpMnQpb/RcCm8r/SJFqKdkQB3Bk0NxtBHwTdw+Bso+Pb06XrNuFFkieag93CSBl9DVL/hqPC+0glPCBcgAe6Iakrh8BY4tAkObYaj35+ZqRgQhY5KIztqKn/KDeC7hmhmXNePB67ugae7nAkihCuRAHcE5Ufg4FdGYB/cBMU7je1unhCZAoN/DFGDIHowRyydeHRFNp/vKiY1JojlU5LpGe5AzaeEEHYjAW6GyuNwYCPkbzCWJw8Y2706Qky6MXYdMxS6Djw9EcZi0byx5SALPvwCi4bHb0ngnqGx5jSfEkI4BAlwe6grN4J636dwYIPRGwSgQyB0G2YcYcdeZZwVcoELBewvrmJ2Rjbf5JcyolcoT09MIjq4jZtPCSEcngR4W2hugqPfGYG971PjQ0fdDJ5+RmCn3g2xI4wzRP7HlV2ami28svEAC9ftxtvDjT9OSWbKwCjbNp8SQjgtCXBbqSmFvetg90fGsq4MUMYY9lW/hh7XQtTgFrdCzT1awcyMTHKOVHBDvwjmT0gkPOAKmk8JIdodCfDW0tpo6rR7rRHah7eAthhXfIm/2bjYQPdR4Bt8WS9b19jMXz7dyz++2EeQrxd/uzOVm5K6tM33IIRwahLgl0NrOLodclfDztXG1WMAOifDiN9B77EQOaDVjZ22HSxl5rIs9hVXMzk1isfG9SXIVy5eIIS4MAnwS7FY4PBma2i/Z1z6S7lD3EgY+nPocyMERF7RLqrrm/jjR7t4dVM+kYE+vHr/YK7uHWajb0AI0V5JgF+I1sbMx+x3IDsDKo+Cu5cxjn3NI0ZoX+bQyMVs3FPMnOXZHCmr5Z4h3Xh4bDz+HeSfRQhxaZIUZzt5ELLfNW7FeeDmYYxlj5kPvcaAd4DNdlVe08iT7+fy7rYCuof58c4DQxkUa5tfCkII1yAB3lhnjGdvexUOfmlsix4CN/8JEiaCX4jNd7k25ziPrcqhtLqBn47qwS+v64W358VPJxRCiAtx3QAvzIXtr0Lm28Ypf51i4Zq5kHybsd4GiirrmLd6Bx9kHyehSwBLpg0isWtgm+xLCNH+uVaAN9VDTgZsXWJ09nP3gvhxMPBeiB3ZZpcF01qTsf0I89fkUtvYzMM39GHGyO7SfEoIcUVcI8CrS2DrYvhmkXE1mtDeMOYp6D+1TYZIzna4tIZHVmSzcc8J0rp1YsHkZHqG+7fpPoUQrqF9B3jxbtj8N8h8C5rqoOf1MPRnxgSbNp6ObrFoXtuUz3Mf7QLgifH9uHtIN9yk+ZQQwkbaZ4AXbIMNzxmzJN07QP87YMhPjUuK2cHeokpmZWSz7eBJRvYO4+mJiUR1kuZTQgjbal8BfiwTPnvaCG6fYBg1B9J+BP72mRTT2Gxh0Yb9vLhuDz5e7vzptv5MSu0qzaeEEG2ifQR44Q4juPPWgHcQXPsYpD8AHex3oYOcI+XMXJZF7rEKbk7qwrzx/QjrKNegFEK0HecO8NL9sH4+7FhhhPWoOTDkQfC236l5dY3NvLR+D//csJ9gPy/+cddAxiZ2ttv+hRCuyzkDvKEGvlwIX71ozJYc8RujL4mNpre31Lf5pcxalsX+E9X8IC2KR29KINBXLiYshLCPKwpwpdRDwHRAA9nAfVrrOlsUdkFaG8Mkax+B8kOQdBtcPx8C7Ntutaq+iefW5vHapoNEdfLh9R+lc1WvULvWIIQQrQ5wpVRX4JdAgta6Vin1DnAHsNRGtZ3rxF74cCbsWw/hCTDtfeMyZHb2+a4iHl2Rw9HyWu4bHsvvxvTBT5pPCSFMcKXJ4wH4KKUaAV/g6JWXdAFf/hk+fdK4wO/YBTDox+Bu39A8Wd3A/PdzWb79CD3D/Vn2k2EM7NbJrjUIIcTZWp2CWusjSqnngUNALfCx1vrj85+nlJoBzACIiYlp3c78Qo3hktHzoGNEa0tuFa01H+Yc5/erciiraeSX1/bkZ9f2pIOHNJ8SQphLaa1b94VKdQIygNuBMuBdYJnW+vWLfU1aWpreunVrq/ZnhqKKOh5blcNHOwpJ6hrIs5OTSYi0XUtZIYRoCaXUNq112vnbr2QcYjRwQGtdbN3BcmAYcNEAdxZaa97dVsCTa3Kpb7Iw+8Z4pl8Vh4c0nxJCOJArCfBDwBCllC/GEMp1gPMcXl/E4dIa5izP5su9JxgcF8yCSUl0D5PmU0IIx3MlY+BblFLLgO1AE/AdsMhWhdlb86nmU2t34e6mePLWRH44OEaaTwkhHNYVncqhtX4ceNxGtZhmT2ElszKy2H6ojFF9wnh6YhKRQT5mlyWEEP+TS5/A3Nhs4R+f7+PlT/fi18GdP9+ewoSUSGk+JYRwCi4b4NkF5Ty8LJO845Xc0j+Sx29JINRfmk8JIZyHywV4XWMzC9ft5pUN+wnr2IFX7knj+gT7nlsuhBC24FIBvnl/CbMzssgvqWHq4Ghm39iXQB9pPiWEcE4uEeCVdY0s+DCPN7YcIibYlzenpzOspzSfEkI4t3Yf4J/lFfHIimwKK+qYflUcvxnTG1+vdv9tCyFcQLtNstLqBv7w3g5Wfn+U3hH+/O3OYQyIkeZTQoj2o90FuNaaNVnHmLd6BxV1jfzqul787JqeeHnINHghRPvSrgL8eHkdc1fmsG5nIf2jAnl2SjrxnaX5lBCifWoXAa615u1vD/P0+ztptFh49Ka+3H9VHO4yDV4I0Y45fYAfLKlmdkY2m/aXMKR7MAsmJRMb6md2WUII0eacNsCbLZolXx3g+Y934enmxtMTk7hjULQ0nxJCuAynDPBdxyuZmZFF5uEyrosP58mJiXQJlOZTQgjX4lQB3tBk4W+f7+Wvn+2lo7cnL96Rwvj+0nxKCOGanCbAvz9cxqxlWewqrGRCSiS/H5dAiDSfEkK4MKcI8JfX72Hhut2Ed/Tm3/emcV1faT4lhBBOEeAxIb7cMTiG2TfGE+AtzaeEEAKcJMAnpHRlQkpXs8sQQgiHIvPLhRDCSUmACyGEk5IAF0IIJyUBLoQQTkoCXAghnJQEuBBCOCkJcCGEcFIS4EII4aSU1tp+O1OqGDhotx22jVDghNlFOBB5P86Q9+Jc8n6c60rej25a67DzN9o1wNsDpdRWrXWa2XU4Cnk/zpD34lzyfpyrLd4PGUIRQggnJQEuhBBOSgL88i0yuwAHI+/HGfJenEvej3PZ/P2QMXAhhHBScgQuhBBOSgJcCCGclAR4CymlopVSnymlcpVSO5RSvzK7JrMppdyVUt8ppdaYXYvZlFJBSqllSqk8pdROpdRQs2syi1LqIevPSI5S6i2llLfZNdmTUmqxUqpIKZVz1rZgpdQnSqk91mUnW+xLArzlmoDfaq0TgCHAz5RSCSbXZLZfATvNLsJBvAis1VrHA/1x0fdFKdUV+CWQprVOBNyBO8ytyu6WAmPP2zYbWK+17gWst96/YhLgLaS1Pqa13m5dr8T4AXXZ67wppaKAm4F/mV2L2ZRSgcBI4N8AWusGrXWZqUWZywPwUUp5AL7AUZPrsSut9Qag9LzNE4BXreuvArfaYl8S4K2glIoFBgBbTC7FTH8GZgIWk+twBHFAMbDEOqT0L6WUn9lFmUFrfQR4HjgEHAPKtdYfm1uVQ4jQWh+zrh8HImzxohLgl0kp5Q9kAL/WWleYXY8ZlFLjgCKt9Taza3EQHkAq8Het9QCgGhv9iexsrGO7EzB+qUUCfkqpu8ytyrFo49xtm5y/LQF+GZRSnhjh/YbWernZ9ZhoODBeKZUPvA1cq5R63dySTFUAFGitT/1Ftgwj0F3RaOCA1rpYa90ILAeGmVyTIyhUSnUBsC6LbPGiEuAtpJRSGGOcO7XWL5hdj5m01nO01lFa61iMD6g+1Vq77FGW1vo4cFgp1ce66Tog18SSzHQIGKKU8rX+zFyHi36ge57VwL3W9XuBVbZ4UQnwlhsO3I1xtPm99XaT2UUJh/EL4A2lVBaQAjxtbjnmsP4VsgzYDmRjZIxLTalXSr0FbAL6KKUKlFI/AhYA1yul9mD8lbLAJvuSqfRCCOGc5AhcCCGclAS4EEI4KQlwIYRwUhLgQgjhpCTAhRDCSUmACyGEk5IAF0IIJ/X/Wc1A+UEq9hoAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "n=linspace(1,10)\n",
    "plt.plot(n,n+6,label='$n+6$')\n",
    "plt.plot(n,log(n)+8, label='$\\log{n}+8$')\n",
    "leg=plt.legend(loc='best')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/d3fzzAAAACXBIWXMAAAsTAAALEwEAmpwYAAAtqElEQVR4nO3deVxVdf7H8deXRVFAUERQQMEVEEUR99TKLDPNLFvMSsulZvpN+0zN2ixNUzPt8/s1jWVqqWmjabu5tJi5JCqCgiIiCsiO7CLL/f7+OFfNRlO593LuvXyej8d9AOdezvlwk3dfvue7KK01Qggh3IuH2QUIIYSwPwl3IYRwQxLuQgjhhiTchRDCDUm4CyGEG/IyuwCAzp0768jISLPLEEIIl7Jr164SrXXw+Z5zinCPjIwkKSnJ7DKEEMKlKKWOXug56ZYRQgg3JOEuhBBuSMJdCCHckFP0uZ9PQ0MDubm51NXVmV2K2/Lx8SE8PBxvb2+zSxFC2JnThntubi7+/v5ERkailDK7HLejtaa0tJTc3FyioqLMLkcIYWcX7ZZRSr2tlCpSSu37wbFOSqkNSqlD1o8drceVUuo1pVSmUipFKZXQ3MLq6uoICgqSYHcQpRRBQUHyl5EQbupS+twXAxN/dOwpYJPWug+wyfo1wPVAH+tjPvAvW4qTYHcseX+FcF8XDXet9Wag7EeHpwJLrJ8vAW76wfF3tGE7EKiU6mqnWoUQwm00WTR//TSN3BO1Djl/c0fLhGit862fFwAh1s/DgJwfvC7Xeuy/KKXmK6WSlFJJxcXFzSxDCCFc098+S+fNb4+wOaPEIee3eSikNnb7uOwdP7TWC7TWiVrrxODg886eFUIIt7R0+1He2nKE2aMiuXN4d4dco7nhXni6u8X6sch6PA+I+MHrwq3H3MratWuZN28et99+O+vXrze7HCGEC/kmo5inP9rP1dFd+P3kWIddp7nh/hEwy/r5LODDHxy/xzpqZgRQ8YPuG7dx00038eabb/LGG2+wcuVKs8sRQriIAwWVPLhsN31D/HltxmA8PRw3qOGi49yVUu8BVwKdlVK5wNPAc8D7Sqk5wFHgNuvLPwMmAZlALXCvA2p2Gs888wwPPvig2WUIIVxAUVUdcxYn4dvWk7dnJ+LX1rHTjC56dq31jAs8Nf48r9WAW6XdzTffTGxsLJs3byY7O5u3336b8ePH89RTT3H99deTkNDsofxCiFbiZH0T85YkUVZTz38eGEnXgHYOv6bTzlB1FqmpqYwaNYrNmzezZs0ali1bRlpaGhs3bqSiooLMzEweeOABs8sUQjgpi0Xz2PvJpORVsODuROLCAlrkui4R7n/6eD9pxyvtes7Ybh14ekr/n3xNbW0tFRUVPProo4Cx3k1gYCAPPfQQDz30kF3rEUK4p+fWHeDzfQX8fnIsE2JDLv4NdiKrQv6EtLQ0hgwZgqenJwApKSnExcWZXJUQwlW8uy2bBZuzuGdkD+4bHdmi13aJlvvFWtiOkpqayqBBg858nZKSwtSpU02pRQjhWjamFfL0R/u5JqYLT0/p3+LLfUjL/Sf8ONz37dsnLXchxEWl5Jbzi/f2EBcW4PAhjxfiEi13s7z00kvnfJ2VlWVSJUIIV5FTVst9i5Po5NuGt2Yl0r6NOTEr4S6EEHZSUdvAvYt3Ut/YxIr5w+ni72NaLRLuQghhB/WNFu5fmsTR0hreuW84vbv4m1qPhLsQQtjIYtH8atVetmeV8fLt8YzsFWR2SXJDVQghbPX3Lw6yNvk4v7yuH9MGh5tdDiDhLoQQNlmyNZs3vjnMzOHd+fmVvcwu5wwJdyGEaKZ1+/L548f7uSYmhD9PjXOqrSsl3IUQohmSsst4eEUygyIC+adJY9l/ioS7EEJcpsyiauYsSaJbYDsWzhpKuzaeZpf0XyTchRDiMhRV1jHr7e/x9lQsuXcYnXzbmF3SeUm4/4ScnByuuuoqYmNj6d+/P6+++upFv8fPz68FKru4yMhIBgwYwKBBg0hMTDS7HCHcQmVdA7MX7eREbT2LZg+je1B7s0u6IBnn/hO8vLx48cUXSUhIoKqqiiFDhjBhwgRiYx237+Gl+vrrr1m8eDGLFy++4Gu++uorOnfu3HJFCeHGTjU2Mf+dJDIKq1g4eygDwltmXfbmkpb7T+jateuZnZb8/f2JiYkhL8/Y7/vmm2/md7/7HWPHjqV79+5s3Ljxv77/pZdeIi4ujri4OF555ZUzx//yl7/Qr18/rrjiCmbMmMELL7xwyecUQrS8Jovm0ZXJbM8q44Vb4xnXN9jski7KNVrunz8FBan2PWfoALj+uUt+eXZ2Nnv27GH48OHA+Xdouuaaa868fteuXSxatIgdO3agtWb48OGMGzeOxsZGVq9ezd69e2loaCAhIYEhQ4Zc0jkvh1KKa6+9FqUU999/P/Pnz2/WeYRo7bTW/Onj/XyWWsDvbojhpsFhZpd0SVwj3E1WXV3NLbfcwiuvvEKHDh0uuEPTD23ZsoVp06bh6+sLGK3yb7/9FovFwtSpU/Hx8cHHx4cpU6YAF9716ceGDx/OqVOnqK6upqys7MySxM8//zzXXXfdOdcPCwujqKiICRMmEB0dzdixY+38zgjh/v73y0ze2XaU+8f2ZO6YnmaXc8lcI9wvo4Vtbw0NDdxyyy3MnDmTm2++GXDMDk2Xes4dO3YAF+9zDwszWhddunRh2rRpfP/99xLuQlymFd8f48UNGdw8OIwnJ0abXc5lkT73n6C1Zs6cOcTExPDYY4+dOX6+HZoGDhx4zveOGTOGtWvXUltbS01NDWvWrGHMmDGMHj2ajz/+mLq6Oqqrq/nkk08u+ZyXqqamhqqqqjOfr1+/XjYZEeIyrd9fwG/WpHJlv2Cenz4QDyebpHQxrtFyN8l3333Hu+++e2ZIIcCzzz5Lamrqmb53OP8OTQkJCcyePZthw4YBMHfuXAYPHgzAjTfeyMCBAwkJCWHAgAEEBARc0jkvVWFhIdOmTQOgsbGRO++8k4kTJzbrXEK0RjuySvnFe3sYEB7I6zMT8PZ0vXaw0lqbXQOJiYk6KSnpnGPp6enExMSYVJFjVVdX4+fnR21tLWPHjmXBggVnRuW0NHd+n4Vojn15FcxYsJ2QAB/ev3+k005SAlBK7dJan3cii7TcTTB//nzS0tKoq6tj1qxZpgW7EOJcR0pqmL3oezq08+bdOc47+/RSSLibYPny5WaXIIT4kYKKOu56awcWDe/MGUbXgHZml2QT1+tIEkIIOyuvrefuhTuoONnAknuH0SvYOZYRsYW03IUQrVrNqUZmL9rJ0bJaltw7zOmXFbhUTt1yd4abve5M3l/R2p1qbOKBpbtIyS3nnzMGO8Xep/bitOHu4+NDaWmpBJCDaK0pLS3Fx8fH7FKEMEVjk4VHViTz7aESnrtlINf1DzW7JLty2m6Z8PBwcnNzKS4uNrsUt+Xj40N4uHNs5itES7JYNE+uTuXzfQX8fnIstyVGmF2S3dkU7kqpR4G5gAZSgXuBrsAKIAjYBdytta6/3HN7e3sTFRVlS3lCCPFftNb8+ZM0Vu/O5ZFr+jDnCvfMmWZ3yyilwoCHgEStdRzgCdwBPA+8rLXuDZwA5tijUCGEsIeXNmSweGs2c6+I4uHxfcwux2Fs7XP3AtoppbyA9kA+cDWwyvr8EuAmG68hhBB28e9vDvPPLzO5Y2gEv70hBqVca72Yy9HscNda5wEvAMcwQr0CoxumXGvdaH1ZLnDexY+VUvOVUklKqSTpVxdCONqyHUf52+cHmDywK3+dNsCtgx1s65bpCEwFooBugC9wyatTaa0XaK0TtdaJwcHOv6uJEMJ1rd2Tx+/W7uPq6C68dNsgPF1shcfmsKVb5hrgiNa6WGvdAHwAjAYCrd00AOFAno01CiFEs32ems/j/9nL8KhOvD4zgTZeTjsC3K5s+SmPASOUUu2V8ffNeCAN+AqYbn3NLOBD20oUQojm+fJAIQ+t2EN8eAALZw3Fx9vT7JJajC197jswbpzuxhgG6QEsAJ4EHlNKZWIMh1xohzqFEOKyfJdZwgNLdxMd2oHF9w3Dt63TTutxCJt+Wq3108DTPzqcBQyz5bxCCGGLndllzF2SRFSQL+/cN4wOPt5ml9TiWkfnkxCi1dibU869i3bSNcCHpXOH09GF12S3hYS7EMJtpB2v5J63v6ejrzfL5g0n2L+t2SWZRsJdCOEWDhZUcdfCHbRv48nyuSNcfrMNW0m4CyFcXmZRFTPf2o63p+K9eSOI6NTe7JJMJ+EuhHBph4urmfHmDpRSLJ83gsjOvmaX5BQk3IUQLiu7pIY739yO1prlc4e7xfZ49tK6Bn4KIdzGsdJaZry5nYYmzXvzRtAnxN/skpyKtNyFEC4np8wI9pMNTSydM5x+oRLsPybhLoRwKbknjGCvqmtg6ZzhxHbrYHZJTknCXQjhMnLKarljwXYqTzawdO5w4sICzC7JaUmfuxDCJZwO9qq6BpbNHcGAcAn2nyItdyGE0zsd7NWnGiXYL5G03IUQTu3cYJeumEslLXchhNM6VirB3lzSchdCOKWjpTXMWLCdmvomCfZmkHAXQjidw8XV3PnmduobLRLszSThLoRwKhmFVdz55g5A8978EUSHyjj25pBwF0I4jbTjldy1cAdeHsYiYL27yMzT5pJwF0I4hX15Fdy1cAftvD1ZPm8EUbK6o01ktIwQwnR7jp1gxpvb8W3jxcr5IyXY7UBa7kIIU+3MLuPeRTvp5NuG5fOGE95RNtqwB2m5CyFM8+2hYu5euIMuHdqy8v4REux2JC13IYQpNqQV8uCy3fQM9mXp3OF09mu9m1k7goS7EKLFfbT3OI+uTCYuLIAl9w4lsH0bs0tyOxLuQogW9f7OHJ78IIWhkZ14e/ZQ/NpKDDmCvKtCiBaz6Lsj/OnjNMb1DeaNu4bQro2n2SW5LQl3IYTDaa35v68yeWF9Btf1D+G1GYNp6yXB7kgS7kIIh9Ja8+xn6bz57RGmDQ7jH9MH4uUpA/UcTcJdCOEwjU0WfrMmlfeTcpk9KpI/TI7Fw0OZXVarIOEuhHCIU41NPPxeMuv2F/Dw+D48ck0flJJgbykS7kIIu6s51cj97+5iS2YJf5gcy31XRJldUqtjU8eXUipQKbVKKXVAKZWulBqplOqklNqglDpk/djRXsUKIZxfeW09M9/awbasUl64NV6C3SS23tV4FVintY4G4oF04Clgk9a6D7DJ+rUQohXIrzjJbf/eRtrxSl6fmcD0IeFml9RqNTvclVIBwFhgIYDWul5rXQ5MBZZYX7YEuMm2EoUQriCzqJpbXt/K8fI6Ft87lOv6h5pdUqtmS8s9CigGFiml9iil3lJK+QIhWut862sKgJDzfbNSar5SKkkplVRcXGxDGUIIs+05doJb39hKfZOFFfNHMKp3Z7NLavVsCXcvIAH4l9Z6MFDDj7pgtNYa0Of7Zq31Aq11otY6MTg42IYyhBBm+vpgEXe+uQN/H29WPTBK9jt1EraEey6Qq7XeYf16FUbYFyqlugJYPxbZVqIQwlmt3ZPH3CVJRHb2ZdXPRhIpm2w4jWaHu9a6AMhRSvWzHhoPpAEfAbOsx2YBH9pUoRDCKS3ccoRHViaTGNmRlfePoIu/j9kliR+wdZz7L4BlSqk2QBZwL8b/MN5XSs0BjgK32XgNIYQTsVg0f/vcWE5gYv9QXrljED7esk6Ms7Ep3LXWyUDieZ4ab8t5hRDO6VRjE0/8J4WP9x7nnpE9eHpKfzxlOQGnJDNUhRCXpOJkA/e/m8T2rDKenBjNA+N6ynICTkzCXQhxUfkVJ5n99k6ySqp5+fZ4pg2WyUnOTsJdCPGTMgqrmPX291TVNbJo9jCu6CNj2F2BhLsQ4oK2ZpZw/9JdtPP2ZOX9I+jfTcawuwoJdyHEea3elctTH6QQGeTLonuHEt6xvdklicsg4S6EOIfWmlc2HuLVTYcY1SuIf901hIB23maXJS6ThLsQ4oz6RgtPrU7hgz15TB8SzrPTBtDGS7bEc0US7kIIACpqG7h/qTHU8bEJffnF1b1lqKMLk3AXQpBTVsu9i3dytLRGhjq6CQl3IVq5pOwy5r+7iyaL5t05wxnRM8jskoQdSLgL0Yqt2ZPLk6tSCevYjoWzEukZ7Gd2ScJO5E6JEK2QxaJ5cf1BHl25l4Qegaz5+SgJ9pZ0qhr2LIWF10LmRodcQlruQrQydQ1NPP6fvXyaks9tieE8c5OMiGkRWkPebti9BPathvpqCOoDTQ0OuZyEuxCtSFFVHfPe2UVKbjm/mRTNvDGy+JfD1ZZBykrY/Q4UpYF3e+g/DRLugYjh4KD3X8JdiFYiNbeCee8kUXGygTfuGiIbWDuSxQJZX8Ged+HAp9BUD2FDYPIrEHcL+HRweAkS7kK0Ah/vPc4vV+0lyLctq342UtaIcZTyY7BnGSQvg4ocaNcREufA4LsgNK5FS5FwF8KNWSyalzZk8L9fZZLYoyNv3D2Ezn5tzS7LvTTUwYFPjBukWV8bx3pdBRP+DNE3gJc577eEuxBuquZUI4+uTGZ9WiG3JYbzl5viaOsl2+HZTf5eI9BT3oe6cgjoDlc+BYPuhMDuZlcn4S6EO8opq2XeO0lkFFbx9JRYZo+KlBun9lBbBqmrjL70ghTwbAsxU4xul6hx4OE8o44k3IVwM99llvA/y3fTZNEsuW8YY/oEm12Sa7M0WW+OLj17czR0IEx6AQZMN/rVnZCEuxBuQmvNwi1HePazdHoF+7HgnkSiOvuaXZbrKsuC5OXGozLPenP0Phg0E7oONLu6i5JwF8INnKxv4tcfpLA2+TgT+4fywm3x+LWVX+/LVl8DaR8arfSj34HygF7j4bpnod/1pt0cbQ75ry+Ei8spq+X+d3eRXlDJE9f25edX9sbDQ/rXL5nWcGw7JC+F/WuNmaOdesLVv4f4GRAQZnaFzSLhLoQL25pZwoPLd9PYpFk4K5Gro0PMLsl1VORBygqj26U0E7x9jZmjg++C7iMcNnO0pUi4C+GCtNb8e3MWf193gJ7Bfiy4e4gs/HUpTo9JT15u3CTVFugxGq54DGKnQlv3eQ8l3IVwMVV1DfzyPyms21/ApAGh/H269K//pNMLdiUvg32roK4CAiJgzBMwaIbRBeOG5F+EEC4ko7CKB97dxdGyWn53QwxzroiS8esXUplvLNiVvBxKDoKXD8TcCINnQuRYpxqT7ggS7kK4iI/2HufJVSn4tvVi2VzZMem8Gurg4GdGoB/eZHS7RIyAKa9B/5vAp/WsqSPhLoSTq2+08LfP01n0XTZDenTk9ZkJhHTwMbss56E15CbB3uXGOul1FdAhzOhHj58BnXubXaEpJNyFcGJ55Sf5n+W72XOsnNmjIvnNpBjZWOO0M6Nd3oPSQ+DVzlgKYNAM61IArXsdHQl3IZzUVweKePT9ZBqbNP93ZwI3DOxqdknmq6+B9E+MVnrWN4CG7qNg9EMQe1OLrJPuKmwOd6WUJ5AE5GmtJyulooAVQBCwC7hba11v63WEaC0amyy8tCGD178+THSoP6/PTGjdwxwtFmO26N73jNmj9dXGqovjfgXxd7jtaBdb2aPl/jCQDpz+X+bzwMta6xVKqTeAOcC/7HAdIdxeUWUdv3hvDzuOlHHH0Aj+eGN/fLxbafdC6WEj0PeuhIpj0MbfuCkafyd0H+n2o11sZVO4K6XCgRuAvwKPKWNM1tXAndaXLAH+iIS7EBe15VAJj6zcQ82pJl68NZ5bhoSbXVLLqy2D/Wtg7wrI/R5Q0PNKGP97iJ4MbdqbXaHLsLXl/grwK8Df+nUQUK61brR+nQucd2EGpdR8YD5A9+7mL2wvhFkamiy8vCGDf31zmF7Bfiyfl0DfEP+Lf6O7aKyHzI1GKz1jnbGkbnCMsZPRgFuhQzezK3RJzQ53pdRkoEhrvUspdeXlfr/WegGwACAxMVE3tw4hXFnuiVoeXpHMrqMnuD0xgqdvjKV9m1YwzuH0rNGUFcbmFyfLoH1nGDrX6EcPHejya7uYzZZ/RaOBG5VSkwAfjD73V4FApZSXtfUeDuTZXqYQ7mfdvgJ+tWovFg2v3jGIqYNcc/XBy1J+zJg1uneFsViXZ1uIngQD74De48HT2+wK3Uazw11r/Wvg1wDWlvsTWuuZSqn/ANMxRszMAj60vUwh3EddQxPPfpbOO9uOMjA8gH/OGEyPIDfeVONkuTHKJWWlMeoFjMW6Rj1kLNbVLtDM6tyWI/7+exJYoZR6BtgDLHTANYRwSRmFVTz03h4OFFQx54oonpwY7Z6Tkk73o6esgIProOkUBPWGq34HA2+Djj3MrtDt2SXctdZfA19bP88ChtnjvEK4C60172w7yrOfpePv48Wi2UO5KrqL2WXZ1+llAFJWGssAnO5HHzIb4m+HbgnSj96CWsGdGyHMVVJ9iidXpbDpQBFX9gvmH9PjCfZ3ne3aLqr0MKS8b4T6iSPG6ov9Jhk3RntdLf3oJpFwF8KBvsko5vH391JZ18DTU2KZPSrSPZborS6G/R8YoZ6XhDEefRyM/aWxvossA2A6CXchHKCuoYnn1x1g0XfZ9A3xY+ncYUSHunjgnao2ltNNWQmHvwLdBCED4NpnIO4WGY/uZCTchbCzfXkVPLIymcyiamaN7MGvJ8W47hICTQ1GkKe+Dwc+hYZaCOgOox82box2iTG7QnEBEu5C2Eljk4U3vjnMKxsPEeTXhnfnDGNMn2Czy7p8WkPO90ag718DtaXgEwgDbzceEcNlXRcXIOEuhB1kl9Tw6PvJ7DlWzpT4bvxlan8C27cxu6zLU5QOqf8xHuXHzt4YHTAdek8ALxf7eVo5CXchbKC1Zvn3x3jmk3S8PZXrzTQtP2YMW0xdBYX7QHkaC3Vd9VuIvgHatqI1btyMhLsQzZRXfpKnVqfw7aESxvTpzN+nD6RrQDuzy7q4mhKjuyV1FeRsN46FD4Pr/w79p4Gfm42/b6Uk3IW4TFpr3k/K4S+fpGPRmmduimPm8O7OPcSxrtK4Ibpv1dmRLl1iYfwfjJEuHSPNrlDYmYS7EJchv+IkT61O5ZuMYkb07MQ/pscT0clJ1xhvOAkZXxiBnrHeWAIgsLuxJd2AWyGkv9kVCgeScBfiEmitWbUrlz9/kkZjk+ZPN/bn7hE98PBwstb66aGL+1YbLfX6KvDtYiwBMGA6hA+VJQBaCQl3IS4i90Qtv1mzj80ZxQyL7MQ/bh3oXKs4Wpoge4sR6OkfwckT4BMA/acaLfTIMeDhouPsRbNJuAtxARaLZumOozz/+QE08McpsdwzMtI5WusWC+TuNAI9bS1UF4K3rzHCJe4WY00XGbrYqkm4C3Eeh4ureWp1CjuzTzCmT2eenTbA/L51reH4btj3AexfC5W5xmYXfSYYXS59rpM9RsUZEu5C/EBjk4UF32bxysZDtPP25IVb47klIcy8kTBaG+PP931gLNR1Ihs8vI1di8b/AfpdL4t0ifOScBfCKjmnnF9/kEp6fiWTBoTyxxv708Xfx5xiCtOMsej7PzC2o1OeEDUWxjwBMZOhXUdz6hIuQ8JdtHpVdQ288MVB3tl+lBB/H964awgT40JbvpDig9ZAXwPFB0B5QOQVMPJBiLkRfDu3fE3CZUm4i1ZLa80X+wt4+qP9FFWdYtbISB6/ti/+Pi24uUTxQaP/fP8aKE4HlLG/6KQXjED3D2m5WoRbkXAXrdLx8pP84cP9bEwvJKZrB/59dyKDIgJb5uLFGcYIl/1roCgNUNB9JFz/D2Ojiw5dW6YO4dYk3EWrUt9oYeGWI7y26RAAv5kUzX2jo/DydPAStkUHrIG+9mwLvftIYz2XmBsl0IXdSbiLVmPr4RL+8OF+MouquTY2hN9PjnXc8EatjSV0Twd6yUGMLpdR0kIXLULCXbi9oso6nvk0nY/2HieiUzvenp3I1dEO6MvWGvL3GrNE0z60jnLxMPrQh80zAt3fhBu1olWScBduq6HJwjvbjvLyhgzqmyw8NL4PP7+yl323vLNYjIlFaR8aj/Kj1mGLY4xRLtGTZQldYQoJd+GWvj1UzJ8+TiOzqJpxfYP50439iexsp/VgLE1wbBukfQQHPoHKPPDwMja5GPsE9LsBfIPscy0hmknCXbiVY6W1PPNpGuvTCuneqT1v3ZPI+Jguts8wbayH7G+NLpcDn0JNsTH1v/d4uPr30G+iTCwSTkXCXbiF2vpG/vX1Yf69OQsvD8Uvr+vHnCuibOuCqa+Fw19C+seQ8TnUVRiLc/W91hjh0udaaOtnvx9CCDuScBcuzWLRrE3O4x9fHCS/oo6bBnXjqetjCA1o5rIBJ8vh0HqjhX5oIzSeBJ9Ao6slZrKx2qK3C2ylJ1o9CXfhsnZklfLMp+mk5lUwMDyA12YMZmhkp8s/UWU+HPwU0j8xul4sjeAXCoNnGiNceowGzxactSqEHUi4C5eTXVLDc58fYN3+AroG+PDy7fFMjQ+7vHXWSzLhwMdG/3nuTuNYp15nR7iEJYKHgyc2CeFAEu7CZZTX1vO/X2ayZFs23p4ePD6hL3PH9KRdm0voVz89ZPHAJ3DgM+ukIqDrILjqd0aXS3C0bEEn3IaEu3B6dQ1NLN6azetfZVJ1qpFbh4Tz+LX9COlwkX71xlNw5Fujy+XAZ1BdYIxBjxwNQ+cYa6EHdm+ZH0KIFtbscFdKRQDvACGABhZorV9VSnUCVgKRQDZwm9b6hO2litamyaJZvTuXlzdkkF9Rx1X9gvnVxGhiuv7E5hS1ZXBogxHomZugvtoY4dLnGuOmaJ8J0L4Z/fJCuBhbWu6NwONa691KKX9gl1JqAzAb2KS1fk4p9RTwFPCk7aWK1kJrzZcHinh+3QEyCquJDw/gpdsGMbLXBSYGlR6GjHVw8HM4uhV0k3FDdMB0I9CjxoK3SZtuCGGSZoe71jofyLd+XqWUSgfCgKnAldaXLQG+RsJdXKLtWaW8uP4gO7NPENXZl9dnJnB9XOi5k5AsTcZN0IOfwcF1Z/vPu8TCFY9Cv0nQbbDcEBWtml363JVSkcBgYAcQYg1+gAKMbpvzfc98YD5A9+7S79naJeeU8+L6g3x7qISQDm35y01x3DE0Au/TS/HWVRoTijLWGePQa0uNKf89RkPifcYM0Y6Rpv4MQjgTm8NdKeUHrAYe0VpX/rCFpbXWSil9vu/TWi8AFgAkJiae9zXC/aXnV/LShgw2pBXSybcNv50Uw90jexgzS8uyIOOLs90tlgZjQlGfa42bob3Hg0+A2T+CEE7JpnBXSnljBPsyrfUH1sOFSqmuWut8pVRXoMjWIoX7ySis4rVNh/g0NR+/Nl48NqEv940Mx68wCb562wj1kgzjxcHRMPLn0HcihA8DTxnkJcTF2DJaRgELgXSt9Us/eOojYBbwnPXjhzZVKNzKwYIqXvvyEJ+l5tPO25PHRgYyJyST9keXwatfwalK8PA2hismzjHWcenU0+yyhXA5tjSBRgN3A6lKqWTrsd9ghPr7Sqk5wFHgNpsqFG7hQEEl/9yUyWepeQxvc5SlPY8wvGkXXrv3GC/wC4XYqdD3OmPp3Lb+ptYrhKuzZbTMFuBC0/nGN/e8wr3sy6tg8cZd1B/cxHXee/m73z58G09AnoLwoXDVb40+9K7xMjtUCDuSzkthd7qpkf1J35CxdS2RJ7byvDqMZxuNpV0QHn2uNcK819UymUgIB5JwF/ZRVYg+vImi3Z/SLmczcbqSWBRFAf1pHPgEnjET8eg2GDzsuMWdEOKCJNxF8zSegmPb4fAmdOYmVOE+FOChO7DFMwG/uIkMHT+d0MBgsysVolWScBeXRmsoOWRMJDr8JWRvgYYaLMqLZPqxseF2sgJHMP7K8UwdHEEbL5kdKoSZJNzFhdWUQNbXcPgryPrK2AgaaAyIZG/HiSwu7MWXdf2Iiwrj/nE9eaJvl8tbU10I4TAS7uKs+lo4ts0I9KyvoSAV0MYs0Khx5Az4H97Oj+TdA2DRmkkDurJ8TE/iIwLNrVsI8V8k3FuzpkbITzZa5VnfQM4OaKo3JhFFDIerfktj1Dg+LQ1l0dYckveU49fWk7tHhnPf6CgiOrU3+ycQQlyAhHtrYrFAURoc2QxHvoHs76C+ynguZAAMmw89r4IeIymp9+K9HcdYuvQohZXFRHX25Y9TYpmeGIFfW/lnI4Szk99Sd6a1sT5L9rfGjkTZW6C2xHiuU09jvfOosRA5BvyC0VqzM/sES1dn8Pm+fBqaNGP6dOa5mwcyrm+w9KcL4UIk3N2J1lCaeW6Y11jXbfPvBr2vgZ7jjDAPjDjzbVV1DazZls2y7cc4WFiFv48XM4f34K4R3endRZYBEMIVSbi7MosFig/A0e+sj61QXWg85xd6NsgjrzBa6ucux8ze3ApW7szhw+Q8auubiAvrwPO3DGBKfDfat5F/GkK4MvkNdiVNjVCQYoxoObrVeJwsM57rEAZR46DHKCPQg3qdd62WEzX1rE3OY+XOHA4UVOHj7cHkgd24a0QP4sMDzt3xSAjhsiTcnVl9LeQlwdFtRqDn7jQ2fAYI7GGsbx452tiNqGPkBRfearJoth0uZWVSDl/sK6C+yUJ8eAB/nRbHlPhudPDxbrmfSQjRIiTcnUllPuRsh2M7jGGJBSlgaQQUhPSH+BnQfYTROu/Q7aKnO1RYxQd78li7J4/8ijoC2nlz5/Du3JYYQWy3Do7/eYQQppFwN0tjPRSmQm4S5HxvPCqOGc95tYOwITD6YWO8ecQwaNfxkk5bWn2Kj/ce54M9eaTkVuDpoRjXN5jf3hDDNTEhxvZ1Qgi3J+HeErSGilzI22V0reQmGZOHGuuM5zuEQXgijPgZdB8OoQPB89K7SqrqGli/v5CPU46z5VAJjRZNXFgH/jA5linx3Qj2b+uYn0sI4bQk3B2htgyO74G83Uag5+06OyTRsy10GwRD5xqbVYQPhYCwy75EXUMTXx4o4qPk43x5sIj6Rgthge2YO6Yn0waH0S9UhjAK0ZpJuNvq5AnI3wvHk41Az0+GE9lnn+/cF3qPN7pZuiVA6ADwatOsS9XWN/L1wWI+31fAl+mF1NQ30dmvLXcO686U+G4kdA+U0S5CCEDC/dJpbYwhz08xbnQWpBqhfuLI2dcEdoeugyDhHmuYDzYW3bJBZV0DX6YX8fm+fL7JKKauwUIn3zZMie/GlPhujOgZhKfMHBVC/IiE+/k0noLig8Y6LIX7oXCfEeY1xWdf0zHS6BtPuNsI9G6D7bZt3PHyk2xKL2RjehHbDpdS32QhpENbbkuMYGJcKMMiO+HlKeulCyEurHWHe1MDlB0xZnmWHITCNCPQSw6BbjJe49kGgvtBn+uMLpXQARAaZ3OL/IcsFk1qXgWb0gvZkF5Een4lAFGdfZk1qgcT47oyOCJQ1nYRQlyy1hHuJ09A6WHrI9MI8uKDxteWhrOvC+wOXfpD9GQIiTU+D+p1WSNXLlVZTT3fHirmm4xiNmeUUFJ9Cg8FiT068evro7kmNoRewX52v64QonVwj3C3NEFVPpw4CuVHofyYcVPzdJifnqIPoDygYxQER0O/642Pwf0gqA+0dVyYNjRZSMkt55uMEr7JKCYltxytIbC9N2P6BHNl32Cuju5CR9/m3WwVQogfcu1w3/0ubHkJynPObYGjjBmcnXpC7FSj9R3UGzr1MvrKmzla5XJYLJr0gkq2Zpay9XAJ3x8po6a+CQ8FgyICeWR8X8b1C2ZAWIDcEBVC2J1rh3v7IOgaDzE3QscexnorHSMhIBy8WnbiTpNFk55fyc7sMr4/Usa2rFLKa43/4fQM9mVaQhijenVmVK8gAttL61wI4ViuHe7Rk4yHCU7WN7E3t5ydR8rYefQEu4+eoPpUIwBhge24JiaEUb2CGNkriK4B7UypUQjRerl2uLcQi0WTVVLN7mPlJOeUk3ysnIOFVTRZNAD9QvyZOqgbw6I6kRjZibBACXMhhLkk3H+kyaI5UlLD/uMV7MurYP/xSlLzKqiqM1rl/m29iI8I5GfjejG4eyBDenSUbhYhhNNp1eFeUdtARlEVBwuMR1p+JWnHKznZYIxxb+PlQXSoP1PiuzEoIpDBEYH0CvaT8eZCCKfn9uGutaa46hRZJTVkFdeQVVxNRlE1GQVVFFTWnXmdf1sv+oX6c/vQCPp360BcWAC9u/jhLTNBhRAuyC3CvbHJQn5FHTllteScqCWn7CTHymo5UlLDkZKaMzc6Adp6edC7ix+jegXRN9SffiH+9Av1p2uAjyy6JYRwGw4Jd6XUROBVwBN4S2v9nCOus3LnMf75ZSb5FXVnbm4CeCjoFtiOqM6+3JIQRs9gP6I6+9Iz2JduAe2kW0UI4fbsHu5KKU/g/4AJQC6wUyn1kdY6zd7XCvJtS0L3jkR0akdEx/ZEdGpPRMf2dA30ke4UIUSr5oiW+zAgU2udBaCUWgFMBewe7tfEhnBNbIi9TyuEEC7PEc3bMCDnB1/nWo+dQyk1XymVpJRKKi4u/vHTQgghbGBa34XWeoHWOlFrnRgcHGxWGUII4ZYcEe55QMQPvg63HhNCCNFCHBHuO4E+SqkopVQb4A7gIwdcRwghxAXY/Yaq1rpRKfU/wBcYQyHf1lrvt/d1hBBCXJhDxrlrrT8DPnPEuYUQQlycDAYXQgg3JOEuhBBuSGmtL/4qRxehVDFw1Ow6bNQZKDG7CCci78dZ8l6cS96Pc9nyfvTQWp93LLlThLs7UEolaa0Tza7DWcj7cZa8F+eS9+Ncjno/pFtGCCHckIS7EEK4IQl3+1lgdgFORt6Ps+S9OJe8H+dyyPshfe5CCOGGpOUuhBBuSMJdCCHckIS7jZRSEUqpr5RSaUqp/Uqph82uyWxKKU+l1B6l1Cdm12I2pVSgUmqVUuqAUipdKTXS7JrMpJR61Pp7sk8p9Z5SysfsmlqKUuptpVSRUmrfD451UkptUEodsn7saK/rSbjbrhF4XGsdC4wAHlRKxZpck9keBtLNLsJJvAqs01pHA/G04vdFKRUGPAQkaq3jMBYWvMPcqlrUYmDij449BWzSWvcBNlm/tgsJdxtprfO11rutn1dh/PL+185TrYVSKhy4AXjL7FrMppQKAMYCCwG01vVa63JTizKfF9BOKeUFtAeOm1xPi9FabwbKfnR4KrDE+vkS4CZ7XU/C3Y6UUpHAYGCHyaWY6RXgV4DF5DqcQRRQDCyydlO9pZTyNbsos2it84AXgGNAPlChtV5vblWmC9Fa51s/LwDstim0hLudKKX8gNXAI1rrSrPrMYNSajJQpLXeZXYtTsILSAD+pbUeDNRgxz+7XY21P3kqxv/0ugG+Sqm7zK3KeWhjXLrdxqZLuNuBUsobI9iXaa0/MLseE40GblRKZQMrgKuVUkvNLclUuUCu1vr0X3KrMMK+tboGOKK1LtZaNwAfAKNMrslshUqprgDWj0X2OrGEu42UUgqjTzVda/2S2fWYSWv9a611uNY6EuNG2Zda61bbMtNaFwA5Sql+1kPjgTQTSzLbMWCEUqq99fdmPK34BrPVR8As6+ezgA/tdWIJd9uNBu7GaKUmWx+TzC5KOI1fAMuUUinAIOBZc8sxj/UvmFXAbiAVI39azVIESqn3gG1AP6VUrlJqDvAcMEEpdQjjL5vn7HY9WX5ACCHcj7TchRDCDUm4CyGEG5JwF0IINyThLoQQbkjCXQgh3JCEuxBCuCEJdyGEcEP/D4xaXHElhcSeAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "n=linspace(1,10)\n",
    "plt.plot(n,n*n, label='$n^2$')\n",
    "plt.plot(n,2*n*log(n)+5, label='$2n\\log{n}+5$')\n",
    "leg=plt.legend(loc='best')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ecuaciones de Recurrencia\n",
    "\n",
    "Al estudiar la eficiencia de algoritmos, a menudo podremos escribir ecuaciones que relacionan el valor de la función en $n$ con los valores de la función en $n-1$, $n-2$, etc. Para que estas ecuaciones tengan solución única, debemos especificar además las *condiciones iniciales*, también llamadas *condiciones de borde*.\n",
    "\n",
    "### Ejemplo: Número de movidas en las Torres de Hanoi\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "a_n &= 2 a_{n-1} + 1 \\text{ para } n\\ge 1\\\\\n",
    "a_0 &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "### Ejemplo: Números de Fibonacci\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "f_n &= f_{n-1}+f_{n-2} \\text{ para } n\\ge 2\\\\\n",
    "f_0 &= 0\\\\\n",
    "f_1 &= 1\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resolución de Ecuaciones Lineales de Primer Orden\n",
    "\n",
    "Consideremos ecuaciones de la forma\n",
    "\n",
    "$$\n",
    "a_{n}=ba_{n-1}+c_{n}\n",
    "$$\n",
    "\n",
    "donde $b$ es una constante distinta de cero y $c_n$ es una función conocida.\n",
    "\n",
    "Para ver cómo resolver este tipo de ecuaciones, a modo de \"precalentamiento\", veamos cómo resolver esta ecuación para el caso $b=1$:\n",
    "\n",
    "$$\n",
    "a_{n}=a_{n-1}+c_{n}\n",
    "$$\n",
    "\n",
    "Esto se puede reescribir como\n",
    "\n",
    "$$\n",
    "a_{n}-a_{n-1}=c_{n}\n",
    "$$\n",
    "\n",
    "y ahora introducimos sumatoria en ambos lados:\n",
    "\n",
    "$$\n",
    "\\sum_{1\\le k \\le n}(a_{k}-a_{k-1})=\\sum_{1\\le k \\le n}c_{k}\n",
    "$$\n",
    "\n",
    "Pero la suma de la izquierda es telescópica, así que el resultado es:\n",
    "\n",
    "$$\n",
    "a_n = a_0 + \\sum_{1\\le k \\le n}c_{k}\n",
    "$$\n",
    "\n",
    "Abordemos ahora el caso general. La idea es tomar la ecuación $a_{n}=ba_{n-1}+c_{n}$ y reducirla de alguna manera al caso $b=1$ que ya sabemos resolver.\n",
    "\n",
    "Para esto, dividiremos ambos lados de la ecuación por el _factor sumante_ $b^n$, obteniendo\n",
    "\n",
    "$$\n",
    "\\frac{a_{n}}{b^n}=\\frac{a_{n-1}}{b^{n-1}}+\\frac{c_{n}}{b^n}\n",
    "$$\n",
    "\n",
    "Si ahora hacemos la sustitución $A_n = a_n/b^n$ y $C_n = c_n/b^n$, la ecuación queda en la forma\n",
    "\n",
    "$$\n",
    "A_{n}=A_{n-1}+C_{n}\n",
    "$$\n",
    "\n",
    "que ya sabemos cómo resolver:\n",
    "\n",
    "$$\n",
    "A_n = A_0 + \\sum_{1\\le k \\le n}C_{k}\n",
    "$$\n",
    "\n",
    "Haciendo ahora la sustitución inversa, obtenemos el resultado:\n",
    "\n",
    "$$\n",
    "a_{n}=a_{0}b^{n}+\\sum_{1\\leq k\\leq n}c_{k}b^{n-k}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo: Número de Movidas en las Torres de Hanoi\n",
    "\n",
    "La ecuación\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "a_n &= 2 a_{n-1} + 1 \\text{ para } n\\ge 1\\\\\n",
    "a_0 &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "tiene como solución\n",
    "\n",
    "$$\n",
    "a_{n}=\\sum_{1\\leq k\\leq n}2^{n-k}=\\sum_{0\\leq k\\leq n-1}2^{k}\n",
    "$$\n",
    "\n",
    "lo cual se simplifica a\n",
    "\n",
    "$$\n",
    "a_{n}=2^{n}-1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resolución de Ecuaciones Lineales Homogéneas con Coeficientes Constantes\n",
    "\n",
    "Consideremos por ejemplo la ecuación de Fibonacci\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "f_n &= f_{n-1}+f_{n-2} \\text{ para } n\\ge 2\\\\\n",
    "f_0 &= 0\\\\\n",
    "f_1 &= 1\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "La siguiente tabla muestra los valores que toma esta función:\n",
    "\n",
    "| $𝑛$  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| $f_n$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |\n",
    "\n",
    "\n",
    "\n",
    "Como se ve, el crecimiento es bastante rápido. Esto es porque este tipo de ecuaciones suele tener soluciones de tipo exponencial, esto es, soluciones de la forma\n",
    "\n",
    "$$\n",
    "f_n = \\lambda^n\n",
    "$$\n",
    "\n",
    "para alguna constante $\\lambda$.\n",
    "Además, si encontramos más de una constante $\\lambda$ para la cual se satisfaga la ecuación, por ser una ecuación lineal, cualquier combinación lineal de esas soluciones también será solución.\n",
    "\n",
    "Si logramos encontrar una solución que cumpla las condiciones iniciales bajo este supuesto, no necesitamos seguir buscando, porque la solucion es única.\n",
    "\n",
    "Sustituyendo $\\lambda^n$ en lugar de $f_n$, y dividiendo ambos lados por $\\lambda^{n-2}$ obtenemos la siguiente ecuación\n",
    "\n",
    "$$\n",
    "\\lambda^{2}-\\lambda-1=0\n",
    "$$\n",
    "\n",
    "llamada la _ecuación característica_ de la ecuación de recurrencia.\n",
    "\n",
    "Resolviendo esta ecuación de segundo grado, obtenemos las raíces\n",
    "\n",
    "$$\n",
    "\\phi=\\frac{1+\\sqrt{5}}{2}\\approx1.618\\ldots,\\qquad\\hat{\\phi}=\\frac{1-\\sqrt{5}}{2}\\approx-0.618\\ldots\n",
    "$$\n",
    "\n",
    "La solución general sería una combinación lineal de estas soluciones:\n",
    "\n",
    "$$\n",
    "f_{n}=A\\phi^{n}+B\\hat{\\phi}^{n}\n",
    "$$\n",
    "\n",
    "La condición inicial $f_0=0$ implica que $B=-A$, y por lo tanto\n",
    "\n",
    "$$\n",
    "f_{n}=A(\\phi^{n}-\\hat{\\phi}^{n})\n",
    "$$\n",
    "\n",
    "La segunda condición inicial, $f_1=1$, implica que\n",
    "\n",
    "$$\n",
    "A(\\phi-\\hat{\\phi})=A\\sqrt{5}=1\n",
    "$$\n",
    "\n",
    "Con lo cual obtenermos la siguiente fórmula para los números de Fibonacci:\n",
    "\n",
    "$$\n",
    "f_{n}=\\frac{1}{\\sqrt{5}}(\\phi^{n}-\\hat{\\phi}^{n})\n",
    "$$\n",
    "\n",
    "Nótese que como $|\\hat{\\phi}|<1$, el aporte del segundo término tiende a cero rápidamente, y $f_n=\\Theta(\\phi^n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def f(n):\n",
    "    r5=math.sqrt(5)\n",
    "    phi=(1+r5)/2\n",
    "    phihat=(1-r5)/2\n",
    "    return 1/r5*(phi**n-phihat**n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55.000000000000014 610.0000000000003 6765.000000000005\n"
     ]
    }
   ],
   "source": [
    "print(f(10), f(15), f(20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El \"ruido\" que es observa en las cifras finales es producto de los errores de truncación al representar irracionales como $\\sqrt{5}$ en punto flotante. Si expandiéramos las fórmulas y simplificáramos, obtendríamos los valores exactos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ejemplo: Número de movidas en las Torres de Hanoi\n",
    "\n",
    "Veamos ahora una nueva manera de resolver la ecuación de Hanoi, la cual podemos rescribir como\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "a_n - 2 a_{n-1} &= 1 \\text{ para } n\\ge 1\\\\\n",
    "a_0 &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "Ésta es una ecuación lineal de coeficientes constantes *no homogénea*, de modo que el método que acabamos de ver no es directamente aplicable.\n",
    "\n",
    "Si definimos el operador $\\Delta$ como $\\Delta a_n = a_{n+1}-a_n$, podemos transformar esta ecuación en una ecuación homogénea aplicando el operador $\\Delta$ a ambos lados:\n",
    "\n",
    "$$\n",
    "\\Delta (a_n - 2 a_{n-1}) = \\Delta 1\n",
    "$$\n",
    "\n",
    "$$\n",
    "(a_{n+1}-2a_n)-(a_n-2a_{n-1})=1-1\n",
    "$$\n",
    "\n",
    "esto es\n",
    "\n",
    "$$\n",
    "a_{n+1}-3a_n+2a_{n-1}=0\n",
    "$$\n",
    "\n",
    "De manera similar, cualquier ecuación de este tipo en que la parte no homogénea es un polinomio en $n$ puede convertirse en una ecuación homogénea por aplicaciones reiteradas del operador $\\Delta$.\n",
    "\n",
    "Si \"pasamos en limpio\" esta ecuación de modo que su término líder sea $a_n$, se ve que la nueva ecuación sólo es válida para $n\\ge 2$, de modo que se necesita una segunda condición inicial, la cual se obtiene sin problemas desde la ecuación original."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## El Teorema Maestro\n",
    "\n",
    "Veremos diversos algoritmos que dan origen a recurrencias de la forma\n",
    "\n",
    "$$\n",
    "T(n)=pT(\\frac{n}{q})+Cn^r\n",
    "$$\n",
    "\n",
    "Para simplificar, supongamos que $n$ es una potencia de $q$, digamos $n=q^k$, para que la división $n/q$ siempre se pueda hacer en forma exacta.\n",
    "Entonces\n",
    "\n",
    "$$\n",
    "T(q^{k})=pT(q^{k-1})+C(q^r)^{k}\n",
    "$$\n",
    "\n",
    "Si introducimos una nueva función incógnita $a_k = T(q^{k})$, podemos reescribir la ecuación como\n",
    "\n",
    "$$\n",
    "a_{k}=pa_{k-1}+C(q^r)^{k}\n",
    "$$\n",
    "\n",
    "la cual es de un tipo que ya sabemos resolver.\n",
    "Su solución es\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "a_{k} & =a_{0}p^{k}+C\\sum_{1\\leq j\\leq k}(q^r)^{j}p^{k-j}\\\\\n",
    "      & = p^k \\left( a_0 + C \\sum_{1\\leq j\\leq k} \\left(\\frac{q^r}{p}\\right)^j \\right)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "El comportamiento de esta sumatoria depende de si el cuociente $q^r/p$ es menor, igual o mayor que $1$.\n",
    "\n",
    "Antes de analizar cada caso, observemos que $n=q^k$ implica que $k=\\log_q{n}$, y\n",
    "\n",
    "$$\n",
    "p^k = p^{\\log_{q}n}=(q^{\\log_{q}p})^{\\log_{q}n}=(q^{\\log_{q}n})^{\\log_{q}p}=n^{\\log_{q}p}\n",
    "$$\n",
    "\n",
    "con lo cual la solución puede escribirse como\n",
    "\n",
    "$$\n",
    "T(n)=n^{\\log_{q}p} \\left( T(1)+C \\sum_{1\\leq j\\leq\\log_{q}n} \\left(\\frac{q^r}{p}\\right)^{j}\\right)\n",
    "$$\n",
    "\n",
    "### Caso $q^r<p$:\n",
    "\n",
    "En este caso, la sumatoria está acotada por una constante, porque la serie respectiva es convergente, de modo que\n",
    "\n",
    "$$\n",
    "T(n)=\\Theta(n^{\\log_{q}p})\n",
    "$$\n",
    "\n",
    "### Caso $q^r=p$:\n",
    "\n",
    "En este caso la sumatoria es logarítmica, y $\\log_q{p}=r$, de modo que\n",
    "\n",
    "$$\n",
    "T(n) = \\Theta(n^r \\log{n})\n",
    "$$\n",
    "\n",
    "### Caso $q^r>p$:\n",
    "\n",
    "En este caso la sumatoria es la suma de una progresión geométrica, que podemos escribir en forma cerrada como\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "T(n) &= n^{\\log_q{p}}\\left( T(1)+C\\frac{q^r}{p}\\frac{\\left( \\frac{q^r}{p} \\right) ^{\\log_q{n}}-1}{\\frac{q^r}{p}-1}  \\right)\\\\\n",
    "     &= \\Theta(n^{\\log_q{p}}+n^r)\\\\\n",
    "     & = \\Theta(n^r) \\text{ porque } \\log_q{p}<r\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "En conclusión, hemos demostrado lo siguiente:\n",
    "\n",
    "### Teorema Maestro\n",
    "\n",
    "La ecuación\n",
    "\n",
    "$$\n",
    "T(n)=pT(\\frac{n}{q})+Cn^r\n",
    "$$\n",
    "\n",
    "tiene solución\n",
    "\n",
    "$$\n",
    "T(n) =\n",
    "\\begin{cases}\n",
    "\\Theta(n^r) & \\text{ si } p<q^r\\\\\n",
    "\\Theta(n^r \\log{n}) & \\text{ si } p=q^r\\\\\n",
    "\\Theta(n^{\\log_q{p}}) & \\text{ si } p>q^r\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}