Introducción a conceptos básicos de análisis de algoritmos.

insercion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eficiencia de programas\n",
    "============"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "import pylab as pl\n",
    "from __future__ import unicode_literals\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problema:\n",
    "--------\n",
    "Ordenar "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "num_datos = 10**7 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "números"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Programas:\n",
    "---------\n",
    "*Programa A*: \n",
    "- Ordenamiento por inserción $O(n^2)$\n",
    "- Buena implementación ($2n^2 \\textrm{inst}$)\n",
    "- Computador rápido: 10 mil millones de instrucciones por segundo ($10^{10} \\frac{\\textrm{inst}}{\\textrm{seg}}$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tiempo_programa_A(n):\n",
    "    return 2.0*(n**2)/(10**10)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Programa B*: \n",
    "- Ordenamiento por mezcla $O(n\\lg n)$\n",
    "- Mala implementación ($50 n\\lg n\\ \\textrm{inst}$)\n",
    "- Computador lento: 10 millones de instrucciones por segundo ($10^{6} \\frac{\\textrm{inst}}{\\textrm{seg}}$)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tiempo_programa_B(n):\n",
    "    return 50.0*n*np.log10(n)/(10**6)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tiempo programa A:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20000.0 segs,  5.55555555556 horas\n"
     ]
    }
   ],
   "source": [
    "ta = tiempo_programa_A(num_datos)\n",
    "print ta, \"segs, \", ta/3600, \"horas\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tiempo programa B:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3500.0 segs,  0.972222222222 horas\n"
     ]
    }
   ],
   "source": [
    "ta = tiempo_programa_B(num_datos)\n",
    "print ta, \"segs, \", ta/3600, \"horas\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x10b170890>,\n",
       " <matplotlib.lines.Line2D at 0x10b170b10>]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZ4AAAEPCAYAAAByRqLpAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XmYVNWd//H3F2SXRZS1FzGKC4Ig0NDNoq1mkIxxm4lx\ni+FR/CV5lJhEo6KZKE4St0zckriM+4rLRI3bqKB0Ag100yyyicIoNN1Ag6yy93J+f5zbRYENNlRX\n3Vo+r+epp2+fqlv1rSvw8Zx77rnmnENERCRRmoVdgIiIZBYFj4iIJJSCR0REEkrBIyIiCaXgERGR\nhFLwiIhIQsU9eMxsuZnNN7O5ZlYatHU2s0lm9rmZfWhmnaJef4uZLTWzJWY2Kqp9kJktCJ57MN51\ni4hIfCSix+OAQufcqc65IUHbeGCSc+544KPgd8ysD3Ax0AcYDTxsZhbs8wgw1jnXG+htZqMTULuI\niDSxRA212T6/nwc8G2w/C1wQbJ8PTHTOVTvnlgPLgKFm1gNo75wrDV73XNQ+IiKSQhLV45lsZmVm\n9v+Ctm7OuapguwroFmz3BCqi9q0AshporwzaRUQkxRyWgM8Y7pxbbWZdgElmtiT6SeecMzOt2yMi\nkiHiHjzOudXBz3Vm9gYwBKgys+7OuTXBMNra4OWVQE7U7tn4nk5lsB3dXrnvZynAREQOnnNu39Mh\ncRXXoTYza2tm7YPtdsAoYAHwFjAmeNkY4M1g+y3gEjNraWbHAL2BUufcGmCLmQ0NJhtcEbXPXpxz\nGf+4/fbbQ68hWR46FjoWOhYHfoQh3j2ebsAbwcS0w4AXnXMfmlkZ8KqZjQWWAz8EcM4tNrNXgcVA\nDXCN23NkrgGeAdoA7znn3o9z7SIiEgdxDR7n3JfAgAbaNwDf3c8+dwJ3NtA+G+jX1DWKiEhiaeWC\nNFRYWBh2CUlDx2IPHYs9dCzCZWGN8cWDmbl0+j4iIvFmZrh0mlwgIiKyLwWPiEiaW78+7Ar2puAR\nEUljX3wBfftC5TeufAyPgkdEJE3t2AE/+AHceitkJdEiY5pcICKSpq6+GrZtg5deAtvP9IEwJhck\nYq02ERFJsCefhOnTobR0/6ETFvV4RETSzNy5MGoUTJ0KJ5544NdqOrWIiMRk40Z/Xuevf/320AmL\nejwiImmirg7OPx+OPRYeeKBx++gcj4iIHLK774YNG+Bvfwu7kgNT8IiIpIHJk+HPf4ayMmjZMuxq\nDkzBIyKS4lasgB/9yE+bTqbrdfZHkwtERFLYzp3w7/8ON94IZ54ZdjWNo8kFIiIpyjkYO9ZfJPry\ny4d2vY4mF4iISKM99pi/QHTmzOS7SPRA1OMREUlBM2b4qdPFxdC796G/jy4gFRGRb7VmDVx0kV8W\nJ5bQCYuCR0QkhVRXww9/6M/tnHtu2NUcGg21iYikkF/+EpYuhbffhmZN0HXQ5AIREdmvF16Ad96B\nWbOaJnTCoh6PiEgKmD0bRo+Gjz+Gfv2a7n01uUBERL6hqgouvBAefbRpQycsCh4RkSS2e7efwTZm\njF+hIB1oqE1EJIldey2Ul8Pf/x6f8zqaXCAiIhFPPAEffQQlJak9mWBf6vGIiCSh6dPhggv87atP\nOCF+n6PJBSIiQmWlP6/z9NPxDZ2wKHhERJJI/W0OrrkGzjkn7GriQ0NtIiJJwjk/e23HDnj11cSs\nOK3JBSIiGey//gsWLoRp01LrNgcHS8EjIpIE3n0X7r/fz2Br2zbsauJLwSMiErLFi+HKK/21Ojk5\nYVcTf5pcICISovXr4bzz4I9/hIKCsKtJDE0uEBEJSXW1X/jz1FP9+Z0wpOV1PGbW3Mzmmtnbwe+d\nzWySmX1uZh+aWaeo195iZkvNbImZjYpqH2RmC4LnHox3zSIiiXD99dCqFdxzT9iVJFYihtp+ASwG\n6rsi44FJzrnjgY+C3zGzPsDFQB9gNPCwWWRexyPAWOdcb6C3mY1OQN0iInHz2GMweTJMnAjNm4dd\nTWLFNXjMLBv4V+AJoD5EzgOeDbafBS4Its8HJjrnqp1zy4FlwFAz6wG0d86VBq97LmofEZGU89FH\ncNtt8NZb0LFj2NUkXrx7PPcDNwJ1UW3dnHNVwXYV0C3Y7glURL2uAshqoL0yaBcRSTmffQaXXQav\nvAK9e4ddTTjiNp3azL4PrHXOzTWzwoZe45xzZtakswEmTJgQ2S4sLKSwsMGPFhFJuPXr4fvfhzvv\nhLD+aSoqKqKoqCicDw/EbVabmd0JXAHUAK2BDsDrQB5Q6JxbEwyjTXHOnWhm4wGcc3cH+78P3A6s\nCF5zUtB+KXC6c+5nDXymZrWJSFLavRvOPhvy8uDee8OuZo+0mtXmnLvVOZfjnDsGuAT42Dl3BfAW\nMCZ42RjgzWD7LeASM2tpZscAvYFS59waYIuZDQ0mG1wRtY+ISNJzzi/62aED3HVX2NWEL5ErF9R3\nRe4GXjWzscBy4IcAzrnFZvYqfgZcDXBNVPflGuAZoA3wnnPu/QTWLSISk/vug7IyvwZbps1ga4gu\nIBURiaO33vK9nRkzknM5HK1OLSKSRubNg6uv9guAJmPohEVrtYmIxEFFhV+D7eGH/YQC2UPBIyLS\nxL7+2k+bHjcOfvCDsKtJPjrHIyLShGpqfE8nJwcefTT5b+iWVtOpRUQyjXNw3XVQWwt/+Uvyh05Y\nNLlARKSJ3HefnzI9bRq0aBF2NclLwSMi0gRef93funr6dH+hqOyfgkdEJEalpfDTn8L770NubtjV\nJD+d4xERicGXX8IFF8BTT8GgQWFXkxoUPCIih2j9en/r6ltvhXPPDbua1KHp1CIih2DHDvjud2HE\niNS+dXUY06kVPCIiB6m2Fi66CFq3hhdegGYpPHaktdpERJKcc3D99bBxo59MkMqhExYFj4jIQbj/\nfvjoI3+tTqtWYVeTmhQ8IiKN9MorPniKi6FTp7CrSV0KHhGRRvjnP+HnP4dJk3StTqw0Oiki8i0W\nLvSTCV56Cfr3D7ua1KfgERE5gBUr4Hvfgwce8NOnJXYKHhGR/Vi/Hs4+289iu/TSsKtJH7qOR0Sk\nAdu2+R7Oaael9gWi30YXkMZIwSMiTaG6Gi68EI48Ep55Jr3vq6MbwYmIhMw5+MlPoK4OnngivUMn\nLJpOLSIS5dZbYfFi+Phj3cwtXhQ8IiKBBx+EN97wqxK0axd2NelLwSMiAjz3HPzpTzB1Khx1VNjV\npDcFj4hkvLfegptugilT4Oijw64m/Sl4RCSj/eMfcPXV8O67cNJJYVeTGTSrTUQy1pw5fimciRMh\nLy/sajKHgkdEMtLnn8M558Bjj8FZZ4VdTWZR8IhIxlm5EkaNgj/8wV8oKoml4BGRjPLVVz50xo2D\nq64Ku5rMpCVzRCRjbN4MZ57pF/68886wq0kOWqstRgoeEdmfbdt84Awc6C8U1VI4noInRgoeEWnI\nzp1w7rmQk+PXX2umkwwRCp4YKXhEZF/V1fCDH0Dr1v4Oos2bh11Rckmr1anNrLWZlZjZPDNbbGZ3\nBe2dzWySmX1uZh+aWaeofW4xs6VmtsTMRkW1DzKzBcFzD8arZhFJL7W1MGaM//n88wqdZBG34HHO\n7QTOcM4NAE4BzjCzEcB4YJJz7njgo+B3zKwPcDHQBxgNPGwWGYV9BBjrnOsN9Daz0fGqW0TSg3Pw\ns5/BmjXw2mvQsmXYFUm9uI50Oue2B5stgebARuA84Nmg/VnggmD7fGCic67aObccWAYMNbMeQHvn\nXGnwuuei9hER+Qbn4IYbYOFCvw5bmzZhVyTR4ho8ZtbMzOYBVcAU59wioJtzrip4SRXQLdjuCVRE\n7V4BZDXQXhm0i4h8g3P+njpTpsB778Hhh4ddkewrrouEOufqgAFm1hH4wMzO2Od5Z2aaDSAiTeaO\nO/yCnx9/DEccEXY10pCErE7tnNtsZu8Cg4AqM+vunFsTDKOtDV5WCeRE7ZaN7+lUBtvR7ZX7+6wJ\nEyZEtgsLCyksLGyKryAiKeDOO+HVV6GoSPfU2Z+ioiKKiopCrSFu06nN7Cigxjm3yczaAB8AdwBn\nA+udc/eY2Xigk3NufDC54CVgCH4obTJwXNArKgGuA0qBd4GHnHPvN/CZmk4tkqH+9Ce/4Oc//gE9\neoRdTeoIYzp1PHs8PYBnzawZ/lzS8865j8xsLvCqmY0FlgM/BHDOLTazV4HFQA1wTVSKXAM8A7QB\n3msodEQkc/35z/DwwwqdVKELSEUkpT32GNx1lx9e69Ur7GpST7r1eERE4uqpp+D3v1fopJpGB4+Z\nHQ7gnNsav3JERBrn6afhttvgo4/g2GPDrkYOxrdex2Nm/YLzMouBxWY228z6xr80EZGGPf00/Pa3\nPnROOCHsauRgNeYC0v8GrnfO5TrncoEbgjYRkYRT6KS+xgRPW+fclPpfnHNFQLu4VSQish8KnfTQ\nmHM8X5rZb4HnAQMuB76Ia1UiIvtQ6KSPxvR4rgK6Aq8DfwO6BG0iIgmh0Ekvjb6OJ1hvzTnntsS3\npEOn63hE0s+TT8Lttyt04iUpbwRnZnlmtgCYDywws0/MbHD8SxORTPfww37RzylTFDrp5Ft7PEHo\nXOOcmxr8PgJ42Dl3SgLqOyjq8YikjwcegAcf9KtMH3NM2NWkr2RduaCmPnQAnHPTzKwmjjWJSIa7\n5x54/HG/9lpubtjVSFNrTI/nAfzinBODpouBnfhZbjjn5sSzwIOhHo9I6vvd7+DFF/05nSzd8jHu\nwujxNCZ4ioDoF1n07865M/bdJywKHpHU5ZyfufbGGz50uncPu6LMkJTBk0oUPCKpyTm46SaYNMk/\nunQJu6LMkZTneMzsCODHQK+o1zvn3HVxrEtEMkRdHVx7LZSV+YkEnTuHXZHEW2MmF7wHzMBPp65j\nn6E2EZFDVVMDV14J5eV+eK1Dh7ArkkRoTPC0cs5dH/dKRCSj7NoFl14KO3bA//4vtG0bdkWSKI1Z\nMuclM/uJmfUws871j7hXJiJpa9s2OO88aNYM3nxToZNpGtPj2Qn8EfgNfqgN/FDbd+JVlIikr82b\n4fvf9zdve+IJOEz3Qc44jZlO/SWQ55z7KjElHTrNahNJbl99BWefDQUF8NBDvscj4UrKtdqApcCO\neBciIumtogJOOw1GjYI//1mhk8ka08ndDswzsynArqBN06lFpNE++8z3dMaNg1//OuxqJGyNCZ43\ng0f9GJamU4tIo5WVwbnnwp13+qnTIo1aucDM2gK5zrkl8S/p0Okcj0hy+fhjuOQSv+Dn+eeHXY00\nJCnP8ZjZecBc4P3g91PN7K14FyYiqe31133ovPaaQkf21pjTexOAocBGAOfcXDSVWkQO4PHH/fmc\nDz6A008PuxpJNo05x1PtnNtktldPrG5/LxaRzOUc3HWXvz7nH/+A3r3DrkiSUWOCZ5GZXQ4cZma9\ngeuA6fEtS0RSTW0tXHcdFBf7R48eYVckyaoxQ20/B07GT6WeCGwBfhnPokQktezYAT/4gZ82/c9/\nKnTkwHQ/HhGJyYYNft213Fx45hlo2TLsiuRgJNX9eMzsL865cWb2dgNPO+fceXGsS0RSQHk5jB4N\n//qvcO+9Wo1AGme/PR4z+9o5197MCht42jnn/hHXyg6BejwiiTN/PpxzDlx/PfzqV2FXI4cqqXo8\nwDIA51xRYkoRkVQxeTJcdplfc+3ii8OuRlLNgYKni5ldj18iZ1/OOXdfnGoSkST29NMwfry/MFTX\n6MihOFDwNAfaJ6oQEUluzsFtt8GLL/prdE48MeyKJFUdKHjWOOfuSFglIpK0du2CsWNh2TKYORO6\ndg27IkllcZ2DYmY5ZjbFzBaZ2UIzuy5o72xmk8zsczP70Mw6Re1zi5ktNbMlZjYqqn2QmS0Innsw\nnnWLyB4bN/pbGmzf7hf9VOhIrA4UPN9tgvevBn7lnDsZyAeuNbOTgPHAJOfc8cBHwe+YWR/gYqAP\nMBp42Pas1fMIMNY51xvobWajm6A+ETmAL7+EYcNg0CB/Tqdt27ArknSw3+Bxzq2P9c2dc2ucc/OC\n7a3Ap0AWcB7wbPCyZ4ELgu3zgYnOuWrn3HL8zLqhZtYDaO+cKw1e91zUPiISB8XFPnTGjYM//Qma\nNw+7IkkXCbvcy8x6AacCJUA351xV8FQV0C3Y7glURO1WgQ+qfdsrg3YRiYPnn4cLL4SnnoJrrw27\nGkk3jVkkNGZmdjjwN+AXzrmvo1e6ds45M9NVnyJJoK4O/uM/4OWXYcoUOPnksCuSdBT34DGzFvjQ\ned4592bQXGVm3Z1za4JhtLVBeyWQE7V7Nr6nUxlsR7dXNvR5EyZMiGwXFhZSWFjYBN9CJP1t2wY/\n/jGsXQslJdClS9gVSTwUFRVRVFQUag1xXSQ0mBjwLLDeOferqPZ7g7Z7zGw80Mk5Nz6YXPASMAQ/\nlDYZOC7oFZXgb8lQCrwLPOSce3+fz9OSOSKHoLLSL/TZrx889hi0ahV2RZIoYSyZE+/gGQH8E5gP\n1H/QLfjweBXIBZYDP3TObQr2uRW4CqjBD819ELQPAp4B2gDvOeeua+DzFDwiB6mszJ/PGTcObroJ\nLKH/BEnY0i54Ek3BI3JwXnjBL/D5+ONwgeaJZqRkWyRURNJUba1fb+311/1Fof36hV2RZBIFj0iG\n2bjRryxdXQ2lpXDkkWFXJJlGt20SySBLlsDQoX6Bz/ffV+hIOBQ8IhninXfgtNPgllvg/vvhMI13\nSEj0R08kzdXVwR/+4KdJ//3vUFAQdkWS6RQ8Imls0yZ/UeiGDTBrFvToEXZFIhpqE0lbCxZAXh70\n6uVnril0JFkoeETS0Msvw5lnwu23w0MPQcuWYVcksoeG2kTSSHU13HyzP5czeTL07x92RSLfpOAR\nSROrV8Mll0C7dv58TufOYVck0jANtYmkgY8/9ncJPessePtthY4kN/V4RFJY/VTpRx7xN28766yw\nK5Jk4Jxj6YalTF0xlWkrpzF1xVT+eeU/6dm+Z9ilAQoekZS1bh1ccQVs3+5XmO6ZHP+mSAhq6mqY\nXzWfqSumMrV8KtPKp9GyeUtGHj2SkbkjuaHgBrof3j3sMiO0OrVICpo+3Z/Puewy+P3vtQpBptlR\nvYOSypJIj2ZmxUyyO2QzImdEJGyO7nR0o95Lt0WIkYJH0l1dHdx3H/zxj/DEE3DuuWFXJImwYccG\nisuLmVruezTzq+bTr2s/RuaOZOTRIxmWM4yj2h51SO+t4ImRgkfS2dq1MGaMX41g4kR/Yaikp/LN\n5b43Uz6NqeVTKd9cTn52PiNyRzAydyRDs4fStkXbJvksBU+MFDySrj76yC99M2YM3HEHtGgRdkXS\nVOpcHYvXLd5rIsDOmp2RIbMRuSMY0H0AhzWLz3iqgidGCh5JN9XVMGECPPMMPPssfPe7YVcksdpV\ns4vZq2dHgqa4vJgj2x4Z6c2MyB1B7869sQTdg1zBEyMFj6STFSvg0kuhQwcfOt26hV2RHIrNOzcz\no2JGJGhmr5rNCUedEJkIMDxnOD3ah7eQnoInRgoeSRevvQbXXgs33gg33ADNdKl3ylj19arI+Zlp\nK6exbMMyBvccHAma/Ox8OrTqEHaZEQqeGCl4JNVt2QI//znMmAEvvABDhoRdkRyIc44lXy2JTAKY\nVj6NLbu2MDx3eGTYbGCPgbRsnryrtCp4YqTgkVQ2fTr86Ef+PM5998Hhh4ddkexrd+1u5qyeEwma\n4vJiOrTqEAmakbkjOeGoE2hmqdNFVfDESMEjqai6Gn73O/jv/4ZHH4ULLgi7Iqm3ZdcWpq+c7ofN\nyqdRtqqM4zofF+nNjMgdQVaHrLDLjImCJ0YKHkk1y5bB5ZfDEUfA00/rZm1hq9xSGQmZaSunsXT9\nUgb1HMTIXD8JYFjOMDq27hh2mU1KwRMjBY+kCufgscfgP/4DbrsNxo3TBIJEq3N1kfMz9Y/NuzYz\nPGfv8zOtDmsVdqlxpeCJkYJHUsHKlTB2LGzcCM89ByedFHZFmaH++pni8uLI9TMdW3f0Q2Y5ftgs\n1c7PNAUFT4wUPJLMnPO3Lvj1r+G662D8eC3uGU+bdm7a6/zMnNVzItfPDM8dzojcEUlzm4AwKXhi\npOCRZFVVBT/9KXzxhe/lDBgQdkXpp3xz+V7DZl9s/IIhWUMiKwLkZ+fTvlX7sMtMOmEEj/5/SySO\nnIP/+R9/bc5VV8Err0Cr9D5lkBC1dbUsWrdor6DZVbsrMmx25YArGdB9AC2aa1G7ZKQej0icrF7t\nVx9YsgSeegry88OuKHVtr97OrMpZkdlmMytm0rVd18iw2cjckRzX+biErW+WTjTUFiMFjyQD5/za\najfdBD/5iZ+51rp12FWllnXb1lG8sjjSm1m4diF9u/aNXDszLGcYXdt1DbvMtKDgiZGCR8JWXu7D\npqrK93JOPTXsipKfc46lG5b62WZBj6ZqaxUFOQWR2WZ5WXlNdv8Z2ZuCJ0YKHglLXZ1fdeC22+D6\n6/3inrpnTsPql52JntbcpkUbhucMj/RoTu5yMs2bNQ+71Iyg4ImRgkfCsGiRn7FWWwtPPgl9+oRd\nUXKpn9ZcXF5M8cpiylaV0fvI3pGgGZ4znJyOOWGXmbEUPDFS8Egi7dgBv/+9X2PtP//Th0+mrz7g\nnGPF5hVMK58W6dEs37ScvJ55kZDJz85Pu2VnUpmmU4ukiMmT4Wc/g4ED4ZNPoGeGXodYU1fDJ2s+\niUwEKF5ZTG1dbWSm2VWnXqVpzfINce3xmNlTwDnAWudcv6CtM/AKcDSwHPihc25T8NwtwFVALXCd\nc+7DoH0Q8AzQGnjPOfeL/XyeejwSV2vX+huzTZ0Kf/0rnHNO2BUl1te7vmZmxcxI0JRWlpLTMScy\nrXl4znC+c8R3NK05haTdUJuZjQS2As9FBc+9wFfOuXvN7GbgCOfceDPrA7wE5AFZwGSgt3POmVkp\nMM45V2pm7wEPOefeb+DzFDwSF7W18PjjfvLAmDEwYQK0axd2VfFXsaVir2GzpeuXMrDHQIbnDGd4\nrl+tuXObzmGXKTFIu6E259xUM+u1T/N5wOnB9rNAETAeOB+Y6JyrBpab2TJgqJmtANo750qDfZ4D\nLgC+ETwi8VBaCtdcA23a+CG2U04Ju6L4qK2rZcHaBXvNNttZszPSk7n8lMuT/m6akhrCOMfTzTlX\nFWxXAd2C7Z7AzKjXVeB7PtXBdr3KoF0krr76Cm65Bd59F+65x98dNJ1GkL7e9TUllSWR2WYllSX0\nbN+T4TnDGfWdUdxReAe9O/fWsJk0uVAnFwTDaE06NjZhwoTIdmFhIYWFhU359pIBoofVLrsMPv0U\nOqbBJKyVm1dSvLI4EjSfrf8sMmz28yE/Z2LORI5se2TYZUqcFRUVUVRUFGoNcZ9OHQy1vR11jmcJ\nUOicW2NmPYApzrkTzWw8gHPu7uB17wO3AyuC15wUtF8KnO6c+1kDn6VzPBKTqVPhl7+Etm395IFU\nHVarratlftV8HzRB2Oyo2eHPzQTnZwb1GJT2NzmTb5d253j24y1gDHBP8PPNqPaXzOw+/FBab6A0\n6BVtMbOhQClwBfBQ4suWdLZihV9bbcYMuPtuuPTS1BpWi55tVryymNLKUrLaZ2nYTJJSvGe1TcRP\nJDgKfz7nNuDvwKtALt+cTn0rfjp1DfAL59wHQXv9dOo2+OnU1+3n89TjkYOydas/f/Pww/7mbDfe\n6Hs7yaz+Is3o1QCWbVi212yzguwCDZtJo6TddOpEU/BIY9XVwQsvwK23QmEh3HUX5CTpqi3VtdXM\nWzOP4pXFPmyiLtIcnuOnNGu2mRwqBU+MFDzSGFOm+J5N8+bw4IPJd5+cDTs2+GGzqLXNjjnimMj5\nmWE5w3SRpjQZBU+MFDxyIAsXws03+xuz3XUXXHRR+Odx6m8JUD9sNr1iOuWbyxmSNYRh2cMYnuvX\nNuvUulO4hUraUvDESMEjDams9FOj33kHfvMbv8Zay5BGpXbW7KRsVVlkyGzGyhm0adGGYTnDIr2Z\nU7qdwmHNtIyiJIaCJ0YKHom2aRP88Y/+Pjk//anv7ST6epw1W9fs1ZuZXzWfPl36REJmWM4wsjtk\nJ7YokSiZMp1aJK62bYOHHoL77oPzzvOrR2cn4N/22rpaFq5dGOnNTF85nU07N0UC5u6z7mZwz8G0\na5kBi7yJHIB6PJI2du6Exx7z1+EUFsIdd8Dxx8fv8zbv3MzMiplMXzmdGRUzIkvODMseFgmbE446\ngWaW4TfpkaSmobYYKXgyU3U1PPMM/O53MGCA/9m/f9N+hnOOZRuWMX3ldP+omM6XG79kcM/BkZDJ\nz87nqLZHNe0Hi8SZgidGCp7MUl3tr8X5wx+gVy9/N9Cmmhq9o3pHZBLA9AofNm0Oa0NBTkHk/Ez/\nbv11gzNJeQqeGCl4MsPu3fDss3DnnXDssfDb38Lpp3/7fgdSsaXCD5mtnMH0iuksXLuQk7ucHOnN\nFGQXkNMxSa8wFYmBgidGCp70tmsXPP20vwbnxBP9FOnhww/+fepXAphRMSMydLajZocPmexhFOQU\nMLjnYNq2SPK1c0SagIInRgqe9LRtGzz5pJ8a3a+fD5yDGVJbu20tM1bOiATNnNVzOLbzsRRkF0R6\nNMcecaxWApCMpOCJkYInvaxfD3/5i789wciRMH485OUdeJ+auhoWrl0YGTKbsXIGX23/ivzs/EjI\nDMkaQodWHRLzJUSSnIInRgqe9FBe7q/Bee45+Ld/8+uqnXBCw69dv309MytmMqPC92hmVc4iq0MW\nBdkF/pFTQJ8ufTSlWWQ/dAGpZLRPPvGB8847cNVVsGABZEXd5Ly2rpbF6xZHQmbGyhms+noVeVl5\nDMsexg0FN5CfnU/nNp3D+xIi8q3U45FQ1dXBu+/C/ffDZ5/BuHF+LbUjjoCNOzZSUlkSOT9TWllK\nl3ZdIrPMCrIL6Nu1L82bNQ/7a4ikLA21xUjBkzq2bvUXfT74IHTqBL/4ZR19Cz+lrGpGJGhWblnJ\n4J6DIyGTn51Pl3Zdwi5dJK0oeGKk4El+X3wBjzwCT760kT7/UkLvM2dQab43c1TboyjIKYgETb9u\n/bRKs0iFNubFAAAMi0lEQVScKXhipOBJTrura3nsjcU89u4Mlu2cSbsTZrCrVQV52Xt6M0Ozh9K1\nXdewSxXJOAqeGCl4ksNX27+ipKKEyZ/N4O25M/li1yxa7e7OoO75XFSQz2nH5Ks3I5IkFDwxUvAk\nXnVtNQvWLohMaZ5ZMZNVm9fSfvMQNi3K5/TvFHDT5UM5q+DIsEsVkQYoeGKk4Im/1V+vZmbFTP+o\nnMmc1XPI7ZhLv04FbF+aT9kb+XS1k7h6bHMuv9zPThOR5KXgiZGCp2ntrNnJnNVzKKkoYWalD5ut\nu7eSn51PflY+A7vls25eHhOf7kRZGVxyCYwdCwMHhl25iDSWgidGCp5D55zji41fMLNiJiWVJcys\nmMnCtQs5qctJDM0aGpnO/J1Ox1FcbLzwAvztb/6+N2PH+hUG2rQJ+1uIyMFS8MRIwdN4m3ZuYlbl\nrEjQlFSW0LJ5y0jA5GfnM7DHwMgKzZ9+6u998+KL0L49XHEFXHop5OhOASIpTcETIwVPw2rqalhQ\ntSASMDMrZrJy80oG9hjI0Kyh5GfnMzR7KNkdsvfa74sv4LXX4JVXoKoKLrvMB84pp4T0RUSkySl4\nYqTg8UNmFVsqIgFTUlnC3NVzyemYw9CsoZGg6du1b4N3z6wPm9deg5Ur/RDaRRf5G60118o0ImlH\nwROjTAyeLbu2ULaqjJKKkkiPpraulqHZQyNBk5eVR6fWnRrc3zk/jPb3v/tzNtFhc9ppcJgutRFJ\nawqeGKV78FTXVrNw7UJKK0sprSylpLKE5ZuW0797/0jIDMkaQq9OvQ54U7OaGiguhrfe8oGzezec\nfz5ceKHCRiTTKHhilE7B45zjy01fRkKmtLKUeWvmcXSnoxmSNYQhPYcwNHso/br2a3DIbF8bNsCk\nSX4l6Pfeg6OPhvPO84HTvz/o5psimUnBE6NUDp5129Yxa9WsvYKm9WGtycvKi/RkBvcc3Og7Z9bW\nwqxZ8MEH8P77sGiR781873s+cDQbTURAwROzVAmerbu3MnvVbGatmhUJm407NpKXlUdezzyGZA0h\nr2ceWR2yvv3NAs7B0qVQVAQff+x7N1lZcPbZMHo0jBgBrVrF7zuJSGpS8MQoGYNnV80u5lfNp2xV\nGaWrSplVOYsvN33JKd1OIa+nD5q8rDyOP/L4g7o9s3N+BlpREUyZ4n+awRln+MeoUXvfvVNEpCEK\nnhiFHTw1dTUsXreYslVlzKr0vZnF6xbT+8jee4VMY8/LRKuu9reGnj7dP4qL/SSB+qA54ww49lid\nqxGRg6PgiVEig6e2rpbP139O2aoy/1hdxidrPiGrQ9ZeITOg+4DI1f+N5RxUVkJZGZSW+qCZPRuO\nOQaGDfOPggI47jgFjYjERsETo3gFT33IzFk9h9mrZzN79Wzmrp5L13ZdGdxzcORxavdT6di640G9\nt3NQUeGDJfoBMGgQ5OXB8OEwdCh0PLi3FhH5Vgqeb2Fmo4EHgObAE865e/Z5Pubgqamr4bOvPtsr\nZOatmUeXtl0Y1HMQg3oEj56D6Nym80G998aNsHChfyxYsGe7RQsfMvWPwYP9+Rn1ZkQk3hQ8B2Bm\nzYHPgO8ClcAs4FLn3KdRrzmo4NlVs4tF6xYxZ/Uc5q6ey5w1c5hfNZ+e7XtyavdTIwEzsMfARofM\nrl3+pP/SpfD55/5Rv/3113DyydC3L/Tr53/27Qtdm/iOz0VFRRQWFjbtm6YoHYs9dCz20LHYI4zg\nSaVr1IcAy5xzywHM7GXgfODTA+1Ub8OODXyy5hPmrZnHvKp5zFszj8/Xf86xRxzLwB4DGdhjIBf3\nvZj+3frvd7jMOdiyBVatgvJyWLHCP6K3q6ogNxeOP94/Tj0VLr4Yevf2184kohejv1R76FjsoWOx\nh45FuFIpeLKAlVG/VwBD933R1t1b+XTdpyxat4hFaxex+KvFLKhawKadm+jfvT/9u/VnZO5Irh38\nc75z+Mns3t6GjRv9MNjG+fD3jf4q/40bfYisWeMf9dstWkCPHv7K/9xc//Nf/mXPdna2f42IiDQs\nlYKnUWNoHX/flbbbT6DN1pNps7UPrbb8hPYb+tLmq2NYsb0Zn26Hp7bDzp3QurU/YX/EEQ0/TjnF\nXw/Tvbt/dOsG7drF+2uKiKS3VDrHkw9McM6NDn6/BaiLnmBgZqnxZUREkogmF+yHmR2Gn1xwFrAK\nKGWfyQUiIpL8UmaozTlXY2bjgA/w06mfVOiIiKSelOnxiIhIemj8qpRJzMxGm9kSM1tqZjeHXc/B\nMLOnzKzKzBZEtXU2s0lm9rmZfWhmnaKeuyX4nkvMbFRU+yAzWxA892BUeyszeyVon2lmR0c9Nyb4\njM/N7MdR7ceYWUmwz8tmlpB5emaWY2ZTzGyRmS00s+uC9ow7HmbWOvjMeWa22MzuytRjEfXZzc1s\nrpm9HfyekcfCzJab2fzgWJQGbal1LJxzKf3AD7stA3oBLYB5wElh13UQ9Y8ETgUWRLXdC9wUbN8M\n3B1s9wm+X4vg+y5jT6+1FBgSbL8HjA62rwEeDrYvBl4OtjsD/wd0Ch7/B3QMnnsV+GGw/QjwswQd\ni+7AgGD7cPw5vZMy+Hi0DX4eBswERmTqsQg+73rgReCtDP978iXQeZ+2lDoWCfkDE+f/CAXA+1G/\njwfGh13XQX6HXuwdPEuAbsF2d2BJsH0LcHPU694H8oEewKdR7ZcAj0a9ZmiwfRiwLti+FHgkap9H\ng/0MWAc0C9rzo49vgo/Lm/iVKjL6eABt8St1nJypxwLIBiYDZwBvZ/LfE3zwHLlPW0odi3QYamvo\nwtJUvxNNN+dcVbBdBXQLtnviv1+9+u+6b3sle45B5Pg452qAzWZ25AHeqzOwyTlX18B7JYyZ9cL3\nBEvI0ONhZs3MbB7+O09xzi0iQ48FcD9wI1AX1Zapx8IBk82szMz+X9CWUsciZWa1HUBaz45wzjlL\n3PVJSXEszexw4G/AL5xzX1vUOkOZdDyCv8gDzKwj8IGZnbHP8xlxLMzs+8Ba59xcMyts6DWZciwC\nw51zq82sCzDJzJZEP5kKxyIdejyVQE7U7znsncqpqMrMugOYWQ9gbdC+73fNxn/XymB73/b6fXKD\n9zoMPya7voH3ygnaNgCdzCK3Q80O2hMiOCn5N+B559ybQXPGHg8A59xm4F1gEJl5LIYB55nZl8BE\n4Ewze57MPBY451YHP9cBb+DXsUytY5GIMck4j3cehj/J1QtoSYpNLgi+Qy++Obng5mB7PN88UdgS\nOCb43vUnCkvwa9cZ3zxR+IjbM44bfaLwC/xJwiPqt4PnXgUudnvGcRN10tSA54D792nPuOMBHBX1\n+W2Af+Ivns64Y7HPcTmdPed4Mu5Y4M/3tQ+22wHFwKhUOxYJ+wMT5/8Y38PPgFoG3BJ2PQdZ+0T8\nSgy78eOqVwb/gScDnwMf1v/HDV5/a/A9lwBnR7UPAhYEzz0U1d4q+EOxFD8zqlfUc1cG7UuBMVHt\nxwR/KJcCrwAtEnQsRuDH8OcBc4PH6Ew8HkA/YE5wLOYDNwbtGXcs9jkup7NnVlvGHYvgM+cFj4UE\n/96l2rHQBaQiIpJQ6XCOR0REUoiCR0REEkrBIyIiCaXgERGRhFLwiIhIQil4REQkodJhyRyRuAjW\np5oc/NodqMUvhujwq/rWNOFnNQNeBzoAK4CrnXO1TfX+IslE1/GINIKZ3Q587Zy7L+xaRFKdhtpE\nGs/M7GozKzV/g7b/MbM2wRPPmNnDZjbDzP7PzArN7FnzN3F7OuoNHjazWeZvdDchqn25mU0ws9nB\nTb5OCNo7m9mbZvZJ8N79Ev6tRZqYgkfk4LzunBvinBsAfAqMDdodfpmSAuBXwFv49bNOBvqZWf/g\ndb9xzuUB/YHTzaxv1P7rnHOD8DfS+nXQfgcw2znXH7/0yXPx/Xoi8afgETk4/cxsqpnNBy7HL8JY\n7+3g50JgjXNukfNj2YvwC8ECXGxms/HrsJ28z/6vBz/nRL1+OPA8gHNuCnBkcNsIkZSlyQUiB+dp\n4Hzn3AIzGwMURj23O/hZB+yKaq8DmpvZMcANwGDn3OZgCK511Ovq96ll77+bhkgaUY9H5OAcDqwJ\n7hv0Ixp/IywD2gPbgC1m1g2/qvq3mYrvWRHcBG2dc27rwRYtkkzU4xE5OLfhl39fF/yMHvZy+9kG\nf2PI+WY2F788/Upg2n4+w0XtPwF4ysw+wYfWmJiqF0kCmk4tIiIJpaE2ERFJKAWPiIgklIJHREQS\nSsEjIiIJpeAREZGEUvCIiEhCKXhERCShFDwiIpJQ/x/2WMgSys3HHQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1094b5050>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "ns = np.arange(1,5*10**6,10**5)\n",
    "pl.ylabel(\"Tiempo\")\n",
    "pl.xlabel('Tamaño')\n",
    "pl.plot(ns, tiempo_programa_A(ns), ns, tiempo_programa_B(ns))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ordenamiento por inserción\n",
    "==========================\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def insertion_sort(A):\n",
    "    j = 1\n",
    "    while j < len(A):\n",
    "        key = A[j]\n",
    "        i = j - 1\n",
    "        while (i >= 0) and (A[i] > key):\n",
    "            A[i + 1] = A[i]\n",
    "            i = i -1\n",
    "        A[i + 1] = key\n",
    "        j = j + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
    "print B\n",
    "insertion_sort(B)\n",
    "print B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Corrección\n",
    "-----------\n",
    "\n",
    "**Invariante de ciclo** \n",
    "\n",
    "_Al comienzo de cada iteración del ciclo externo el subarreglo $A[0..j-1]$ consiste de los elementos originalmente en $A[0..j-1]$  pero ordenados._\n",
    "\n",
    "La siguiente función implementa la comprobación correspondiente al invariante de ciclo.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def invariant(A, original_A):\n",
    "    l1 = list(A)\n",
    "    l2 = list(original_A)\n",
    "    l2.sort()\n",
    "    return l1 == l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invariant([1, 2, 3, 4], [4, 3, 2, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invariant([1, 2, 3, 4], [5, 3, 2, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "invariant([ 2,1, 3, 4, 4], [4, 3, 2, 1, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La siguiente función incluye aserciones para verificar que el invariante de ciclo se cumpla. Si la función es correcta, estas aserciones no deberían fallar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def right_insertion_sort(A):\n",
    "    original_A = list(A)\n",
    "    j = 1\n",
    "    assert invariant(A[0:j], original_A[0:j])\n",
    "    while j < len(A):\n",
    "        assert invariant(A[0:j], original_A[0:j])\n",
    "        key = A[j]\n",
    "        i = j - 1\n",
    "        while (i >= 0) and (A[i] > key):\n",
    "            A[i + 1] = A[i]\n",
    "            i = i -1        \n",
    "        A[i + 1] = key\n",
    "        j = j + 1\n",
    "    assert invariant(A[0:j], original_A[0:j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
    "right_insertion_sort(B)\n",
    "print B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La siguiente función incluye un error, por lo tanto la aserción para comprobar el invariante de ciclo falla.\n",
    "Esto genera una excepción que es capturada para imprimir un mensaje y el estado de las variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def wrong_insertion_sort(A):\n",
    "    original_A = list(A)\n",
    "    j = 1\n",
    "    try:\n",
    "        assert invariant(A[0:j], original_A[0:j])\n",
    "        while j < len(A):\n",
    "            assert invariant(A[0:j], original_A[0:j])\n",
    "            key = A[j]\n",
    "            i = j - 1\n",
    "            while (i >= 0) and (A[i] < key):\n",
    "                A[i + 1] = A[i]\n",
    "                i = i - 1        \n",
    "            A[i + 1] = key\n",
    "            j = j + 1\n",
    "        assert invariant(A[0:j], original_A[0:j])\n",
    "    except  AssertionError:\n",
    "        print \"Error en el invariante de ciclo!\"\n",
    "        print \"j=\", j\n",
    "        print \"i=\", i\n",
    "        print \"A=\", A\n",
    "        print \"Original A=\", original_A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error en el invariante de ciclo!\n",
      "j= 2\n",
      "i= 0\n",
      "A= [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
      "Original A= [5, 4, 6, 3, 7, 2, 8, 1, 9]\n"
     ]
    }
   ],
   "source": [
    "B = [5, 4, 6, 3, 7, 2, 8, 1, 9]\n",
    "wrong_insertion_sort(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Análisis del tiempo de ejecución\n",
    "--------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Counter:\n",
    "    '''\n",
    "    Class Counter\n",
    "    Implements a step counter, which is used to compute the number of basic operations performed in\n",
    "    a particular call to a function.\n",
    "    '''\n",
    "    def __init__(self):\n",
    "        self.steps = 0\n",
    "\n",
    "    def reset(self):\n",
    "        self.steps = 0\n",
    "\n",
    "    def count(self):\n",
    "        self.steps += 1\n",
    "\n",
    "    def print_steps(self):\n",
    "        print \"Number of steps =\", self.steps\n",
    "        \n",
    "def acct_insertion_sort(A, acct):\n",
    "    j = 1; acct.count()\n",
    "    acct.count()\n",
    "    while j < len(A):\n",
    "        acct.count()\n",
    "        key = A[j]; acct.count()\n",
    "        i = j - 1; acct.count()\n",
    "        acct.count()\n",
    "        while (i >= 0) and (A[i] > key):\n",
    "            acct.count()\n",
    "            A[i + 1] = A[i]; acct.count()\n",
    "            i = i -1; acct.count()\n",
    "        A[i + 1] = key; acct.count()\n",
    "        j = j + 1; acct.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of steps = 104\n"
     ]
    }
   ],
   "source": [
    "B = [5, 4, 6, 3, 7, 2, 8, 1, 9,10]\n",
    "acct = Counter()\n",
    "acct_insertion_sort(B, acct)\n",
    "acct.print_steps()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ahora vamos a analizar el comportamiento del algoritmo cuando el tamaño de la entrada varía. La siguiente función genera arreglos al azar de tamaño 1 a n, llama la función `acct_insertion_sort(l, acct)` y contabiliza el número de pasos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import random as rnd\n",
    "\n",
    "def exper_analysis(n):\n",
    "    results = []\n",
    "    acct = Counter()\n",
    "    for i in range(n):\n",
    "        l = range(i)\n",
    "        rnd.shuffle(l)\n",
    "        acct.reset()\n",
    "        acct_insertion_sort(l, acct)\n",
    "        results.append(acct.steps)\n",
    "    return results\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 2, 8, 17, 26, 41, 65, 71, 74, 95]\n"
     ]
    }
   ],
   "source": [
    "print exper_analysis(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x10b547510>]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEACAYAAAC+gnFaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAHgFJREFUeJzt3X+QVed93/H3xxLIIEveoVB+SbKos1SsaxsJKtTULlep\noq53HMG0swJpomFi7B2VpJLTqWTwTKvtH02lzGQiZTJihtgyyGPUrJRYRQ0gFsxVO2ol7EQkWJgA\nnUAMzi7GAeEmzRSsb/+4zy6H1e7du7v3557Pa2aHc5/7nHvPPTOc7znP9/mhiMDMzPLrQ40+ADMz\naywHAjOznHMgMDPLOQcCM7OccyAwM8s5BwIzs5wbNxBIelzSEUnfl/R4KpsjqV/ScUn7JLVl6m+R\ndELSMUn3Z8pXpM85Iem52vwcMzObqLKBQNI/Ar4I/GPg08DnJX0c2Az0R8RS4EB6jaQOYB3QAXQC\nz0tS+ritwMaIaAfaJXXW4PeYmdkEjfdEcAfwdkT8XUT8DHgD+FfAA8COVGcHsDZtrwFeiojLEXEK\nOAmskrQQuCkiDqV6L2b2MTOzBhovEHwf+GxqCpoNdAG3APMjYjDVGQTmp+1FwJnM/meAxaOUn03l\nZmbWYNeXezMijkl6BtgH/A1wGPjZiDohyfNUmJm1qLKBACAiXgBeAJD0nyjd2Q9KWhARA6nZ51yq\nfha4NbP7Lan+2bSdLT872vc5qJiZTVxEaPxao6uk19DfT//eBvxLYCewC9iQqmwAXk3bu4D1kmZK\nWgK0A4ciYgC4JGlVSh4/ktnnAyIi939PPfVUw4+hWf58LnwufC7K/03VuE8EwCuS/h5wGdgUEe9J\nehrok7QROAU8mC7gRyX1AUeBK6n+0FFuArYDs4DdEbF3ykdvZmZTVknT0D8bpeyvgfvGqP8bwG+M\nUv7HwCcncYxmZlZDHlncpAqFQqMPoWn4XFzlc3GVz0X1qBrtS9UkKZrtmMzMmpkkopbJYjMzm94c\nCMzMcs6BwMws5xwIzMxyzoHAzCznHAjMzHLOgcDMLOccCMzMcs6BwMysBnp6eigUCnR1dXHx4sVG\nH05ZDgRmZjVw/Phx3njjDfbs2UNPT0+jD6csBwIzsxqYPXs2ACtXrmTbtm0NPpryPNeQmVkNXLx4\nkZ6eHrZt20ZbW1tNv2uqcw05EJiZtThPOmdmZlNSyVKVWyS9K+mIpJ2SbpA0R1K/pOOS9klqG1H/\nhKRjku7PlK9In3FC0nO1+kFmZtNdtXsklQ0Ekm4HvgTcFRGfBK4D1gObgf6IWAocSK+R1AGsAzqA\nTuD5tEYxwFZgY0S0A+2SOqd89GZmOVTtHknjPRFcorRW8WxJ1wOzgR8BDwA7Up0dwNq0vQZ4KSIu\nR8Qp4CSwStJC4KaIOJTqvZjZx8zMJqDaPZLKBoK0NvFvAX9JKQBcjIh+YH5EDKZqg8D8tL0IOJP5\niDPA4lHKz6ZyMzOboJ07d9Ld3U1/f39VeiSVXbxe0seBLwO3A+8BL0v65WydiAhJVe3m09vbO7xd\nKBS8NqmZWcbhw4fp6Ojg2Wefrcrnle0+Kmkd8IsR8cX0+hHgHuAXgHsjYiA1+xyMiDskbQaIiKdT\n/b3AU8DpVGdZKn8IWB0Rj47yne4+amY2AbXuPnoMuEfSrJT0vQ84CrwGbEh1NgCvpu1dwHpJMyUt\nAdqBQxExAFyStCp9ziOZfczMrIHKNg1FxJ9KehH4HvA+8CfANuAmoE/SRuAU8GCqf1RSH6VgcQXY\nlLm93wRsB2YBuyNib9V/jZmZTZhHFpuZtTiPLDYzsylxIDAzyzkHAjOznHMgMDPLOQcCM7OccyAw\nM8s5BwIzs5xzIDAzyzkHAjOzFlDtxWiyHAjMzBqo0gt8tRejyXIgMDNroEov8NVejCbLgcDMrIGy\nF/hZs2aN+XRQ7cVosjzpnJlZA128eJGenh62bdvG2rVreeONNwDo7u6mr6+vos+Y6qRzZaehNjOz\n2mpraxu+4Ney+accPxGYmTWJ7NPBRJp/pvpE4EBgZlZjPT09HD9+nNmzZ7Nz587qt/HXej0CSf9Q\n0juZv/ckPSZpjqR+Sccl7ZPUltlni6QTko5Juj9TvkLSkfTec5M9aDOzVlLLrp/VMG4giIg/j4g7\nI+JOYAXwt8C3gc1Af0QsBQ6k10jqANYBHUAn8HxapxhgK7AxItqBdkmd1f5BZmbNplFt/5WaaPfR\n+4CTEfFD4AFgRyrfAaxN22uAlyLickScAk4CqyQtBG6KiEOp3ouZfczMpq1adv2shon2GloPvJS2\n50fEYNoeBOan7UXAW5l9zgCLgctpe8jZVG5mNq1lewY1o4oDgaSZwC8BXxn5XkSEpKpleHt7e4e3\nC4UChUKhWh9tZtbyisUixWKxap9Xca8hSWuAfx0Rnen1MaAQEQOp2edgRNwhaTNARDyd6u0FngJO\npzrLUvlDwOqIeHTE97jXkJnZBNS811DGQ1xtFgLYBWxI2xuAVzPl6yXNlLQEaAcORcQAcEnSqpQ8\nfiSzj5mZNUhFTwSSbqR0R78kIn6ayuYAfcBtwCngwYi4mN77KvAF4ArweES8nspXANuBWcDuiHhs\nlO/yE4GZNY1ajwGoBg8oMzOroUKhMKn5f+qpnk1DZma5U+kYgFouHFNrDgRmZmVUOgag2UcPl+PZ\nR83Myqh0DECzjx4uxzkCM7MqmOzModXgZLGZWQupRS8kJ4vNzFpIM+YSHAjMzOqoGXMJbhoyM6tQ\nNZp1apFLcI7AzKxO6jm4bCJBxzkCM7M6qWezTj1zCQ4EZmYVqucCM/UMOm4aMjNrQhPJJThHYGbW\nIM0yM6lzBGZmDdKMYwImw4HAzGySmnFMwGS4acjMbJIaOb9QVl1yBJLagK8BnwAC+BXgBPD7wMf4\n4AplWyitUPYz4LGI2JfKh1Yo+zClFcoeH+W7HAjMzCagXjmC5yhduJcBnwKOAZuB/ohYChxIr5HU\nAawDOoBO4Pm0RjHAVmBjRLQD7ZI6J3vgZma10sqLzEzGuIFA0keBz0bECwARcSUi3gMeAHakajuA\ntWl7DfBSRFyOiFPASWCVpIXATRFxKNV7MbOPmVnDjLzwT5ckcKUqWZhmCfBjSd8APg38MfBlYH5E\nDKY6g8D8tL0IeCuz/xlgMXA5bQ85m8rNzBpq6MIPpaAwXZLAlaokEFwP3AX8WkR8V9KzpGagIRER\nkqrWsN/b2zu8XSgUKBQK1fpoM7MPGO3C3wxJ4LEUi0WKxWLVPm/cZLGkBcD/iogl6fVngC3APwDu\njYiB1OxzMCLukLQZICKeTvX3Ak8Bp1OdZan8IWB1RDw64vucLDazumqW3j+TVfNkcUQMAD+UtDQV\n3Qe8C7wGbEhlG4BX0/YuYL2kmZKWAO3AofQ5lyStSsnjRzL7mJk1zNC6xK0YBKqh0sXr/w3wLUkz\ngf9NqfvodUCfpI2k7qMAEXFUUh9wFLgCbMrc4m+i1H10FqVeSHur9DvMzGySPKDMzHKjWeYGqjbP\nNWRmVqG8dQutlAOBmeVG3rqFVspNQ2aWG63eO2gsXo/AzCznnCMwM7MpcSAwM8s5BwIzs5xzIDAz\nyzkHAjNrCXlbI6CeHAjMrCV4MFjtOBCYWUvwYLDa8TgCM2sJ03UwWDV4QJmZWc5NNRBUOg21mVlL\nyM4wOm/ePE6fPj3tZhutNgcCM5tWsusPz507l/PnzwOlANHX1zdcb7pOST0ZFSWLJZ2S9GeS3pF0\nKJXNkdQv6bikfZLaMvW3SDoh6Zik+zPlKyQdSe89V/2fY2Z5l00qL1++fHh7ZILZvZCuqrTXUACF\niLgzIu5OZZuB/ohYChxIr5HUAawDOoBO4Pm0NCXAVmBjRLQD7ZI6q/Q7zMwA2LlzJ93d3fT39/Py\nyy8Pb4+843cvpKsqShZL+gtgZUT8JFN2jNLi84NpgftiWrx+C/B+RDyT6u0FeiktXv+dzOL16ykF\nFy9eb2Z1N516IdVr9tEA9kv6nqQvpbL5ETGYtgeB+Wl7EXAms+8ZYPEo5WdTuZlZ3eV9wfqsSpPF\n/zQi/krSPKA/PQ0Mi4iQ5Nt4M7MWVFEgiIi/Sv/+WNK3gbuBQUkLImJA0kLgXKp+Frg1s/stlJ4E\nzqbtbPnZ0b6vt7d3eLtQKFAoFCo5TDOzXCgWixSLxap93rg5Akmzgesi4qeSbgT2Af8RuA/4SUQ8\nI2kz0BYRm1OyeCelYLEY2A/8XHpqeBt4DDgE/BHwOxGxd8T3OUdgZjYB9RhQNh/4dur4cz3wrYjY\nJ+l7QJ+kjcAp4EGAiDgqqQ84ClwBNmWu7JuA7cAsYPfIIGBmZvXnKSbMrGl4kNfkeM1iM5s2Kh3k\n5bUJqsuBwMyaRqWDvDwquLocCMysaWRHBZdrFvKo4OpyjsDMaqJce/9UcwHTaVRwNXg9AjNrSoVC\nYXgW0O7u7mtm/iz33mTkPcnsZLGZNaVyzTfVbtpxzmBqHAjMrCbKtfdXmguotHeQcwZT46YhM2uo\ncs06lTYh5T1n4KUqzaylZVcUG7mKWKV3+kMzidrkuGnIzBqq3MW+0iYkmxo3DZlZQ+W9Waca3H3U\nzGou790zm527j5pZzbl75vTmQGBm4xqrHd+Tv00PDgRmNq6xkraeLXR6cPdRMxvXWN0zJzpbKHyw\ni6g1XkVPBJKuk/SOpNfS6zmS+iUdl7RPUlum7hZJJyQdk3R/pnyFpCPpveeq/1PMrB6yd/dbt269\n5klhrDt/j/xtchEx7h/wb4FvAbvS698EnkzbXwGeTtsdwGFgBnA7cJKrPZMOAXen7d1A5xjfFWbW\nvFavXh1AANHd3V3RexcuXIju7u64cOFCvQ83F9J1s6Lr+Wh/4z4RSLoF6AK+Bgx1T3oA2JG2dwBr\n0/Ya4KWIuBwRp1IgWCVpIXBTRBxK9V7M7GNmLWQyk8kNNS2522lzqqRp6LeBJ4D3M2XzI2IwbQ9S\nWuAeYBFwJlPvDLB4lPKzqdzMWkw1JpOz5lI2WSzp88C5iHhHUmG0OhERkjwCzCwnys3r4zl/WtN4\nvYZ+HnhAUhfwYeBmSd8EBiUtiIiB1OxzLtU/C9ya2f8WSk8CZ9N2tvzsWF/a29s7vF0oFCgUChX9\nGDOzPCgWixSLxap9XsVTTEhaDfy7iPglSb8J/CQinpG0GWiLiM2SOoCdwN2Umn72Az+XnhreBh6j\nlDT+I+B3ImLvKN8TlR6TmZnVfxrqoSv000CfpI3AKeBBgIg4KqkPOApcATZlruqbgO3ALGD3aEHA\nzMzqz5POmZm1OE86Z2ZmU+JAYGaWcw4EZmY550BgZpZznn3ULEfKrTSWfW/evHmcPn3aK5LlhHsN\nmU1z2Qv8pUuXePPNNwHo7u6+ZhRwoVAYnip67ty5nD9/ftR61nzqPY7AzFpMdi2ABQsWAONPGNfW\n1sb+/fs9bXROOEdgNs1lL/BvvfVWRRPGvfzyy548LkfcNGQ2zV28eJGenh62bdvmi/o0NdWmIQcC\ns2mmXEJ4MvWs+TkQmE0zk7mQZ3v5lEsIZ2WTw04ItzYni82mmUoXes/Wy/byKZcQzvI6wjbEyWKz\nJlPpBTpbb/ny5cPb5RLCWV5NzIa4acisyVSa3M3WA5wQzjHnCMzMcs7TUJuZ2ZSUDQSSPizpbUmH\nJR2V9J9T+RxJ/ZKOS9onqS2zzxZJJyQdk3R/pnyFpCPpvedq95PMzGwiygaCiPg74N6IWA58CrhX\n0meAzUB/RCwFDqTXpDWL1wEdQCfwvKShx5WtwMaIaAfaJXXW4geZmdnEjNs0FBF/mzZnAtcBF4AH\ngB2pfAewNm2vAV6KiMsRcQo4CayStBC4KSIOpXovZvYxM7MGGjcQSPqQpMPAIHAwIt4F5kfEYKoy\nCMxP24uAM5ndzwCLRyk/m8rNzKzBxh1QFhHvA8slfRR4XdK9I94PSVXt5tPb2zu8XSgUKBQK1fx4\nM7OWViwWKRaLVfu8CXUflfTvgf8LfBEoRMRAavY5GBF3SNoMEBFPp/p7gaeA06nOslT+ELA6Ih4d\n5TvcfdTMbAJq2n1U0tyhHkGSZgG/CLwD7AI2pGobgFfT9i5gvaSZkpYA7cChiBgALklalZLHj2T2\nMTOzBhqvaWghsEPShygFjW9GxAFJ7wB9kjYCp4AHASLiqKQ+4ChwBdiUub3fBGwHZgG7I2JvtX+M\nWSuqdPlIzxBqteKRxWYNVm4W0Ox7S5Ys4bbbbnNQsA/w7KNmLSh7pz9jxgxg/OUjb7jhhopmJTWb\nKE8xYdYAQ1NI79mzhxtvvLGi5SNvvvlmwNNGW/W5acisAbq6utizZw8rV66seBpoLzlpY/Hso2Yt\nyBd1qyYHAjOznPM01GZmNiUOBGY10tPTQ6FQoKura7gpKPvarFm4acisRkaODzh37tyY4wXMpsJN\nQ2ZNauQi9JUuSm9Wb34iMKui7ECxrVu38sQTTwz3DHJPIasV9xoyq7Ny8/+Umy7CrFbcNGRWZ9lR\nwT09Pde85+Yfa0UOBGYTVO5in50Sws0/1ircNGQ2QW7rt2bjHIFZg3nNAGs05wjMGqxczsCsFYwb\nCCTdKumgpHclfV/SY6l8jqR+Sccl7Rta0jK9t0XSCUnHJN2fKV8h6Uh677na/CSz+nKC2FpdJU8E\nl4Ffj4hPAPcAvyppGbAZ6I+IpcCB9BpJHcA6oAPoBJ5P6xQDbAU2RkQ70C6ps6q/xqwBnCC2Vjfh\nHIGkV4HfTX+rI2JQ0gKgGBF3SNoCvB8Rz6T6e4Fe4DTwnYhYlsrXA4WIeHTE5ztHYE3HeQBrZnXN\nEUi6HbgTeBuYHxGD6a1BYH7aXgScyex2Blg8SvnZVG7W9JwHsOms4jWLJX0E+APg8Yj46dXWHoiI\nkFS12/je3t7h7UKhQKFQqNZHm02K8wDWTIrFIsVisWqfV1HTkKQZwH8D9kTEs6nsGKWmnQFJC4GD\nqWloM0BEPJ3q7QWeotQ0dDDTNPQQpaYlNw1Z0/PYAWtmNW8aSonerwNHh4JAsgvYkLY3AK9mytdL\nmilpCdAOHIqIAeCSpFXpMx/J7GPWdLLrBwD09fU5CNi0NO4TgaTPAP8d+DNgqPIW4BDQB9wGnAIe\njIiLaZ+vAl8ArlBqSno9la8AtgOzgN0R8dgo3+cnAquqySZ6PYGctQqPLDYbR7kLejZIzJs3j9On\nTw8HjIcffpg9e/awcuVKdw21pjbVQFBxstisVZVL9A71BgKYO3cu58+fB0oBYufOnc4LWC54igmb\n9soN+MoGieXLlw9vD138nRewPHDTkOVatjcQ4CcAa0nOEZhNkEcJ23Tj2UfNJsijhM2u5UBg00K2\nz//FixfL1vUoYbNrORBY05nIRX3IRO7yPVuo2bXcfdSaTrZLZ09PT0UDuUbe5ZfLAwz1BjKzEj8R\nWNOZTNPNyLt85wHMKudeQ9Z0yk3wVmmPn66uLo8Kttxw91HLlex0EUuWLOG2224bNSh4tlDLE08x\nYdNCpXf62WajG264YcxcgvMAZpVzjsDqplxvoErb9LO5gJtvvhlwN1CzqXIgsLopd7GvNEGcnf/H\n3UDNqsM5Aqubcgncsdr0PR2E2ficLLaWkb3YP/nkkxVd4L04jNn46rFU5QuSBiUdyZTNkdQv6bik\nfZLaMu9tkXRC0jFJ92fKV0g6kt57brIHbK0r26xTaU7A00GY1V4lOYJvAJ0jyjYD/RGxFDiQXiOp\nA1gHdKR9nk/rEwNsBTZGRDvQLmnkZ9o0MDIhPFaCuNILvPMAZrVXUdOQpNuB1yLik+n1MWB1RAxK\nWgAUI+IOSVuA9yPimVRvL9ALnAa+ExHLUvl6oBARj47yXW4aamEjm3LOnTs3atOO+/mbVU+jpqGe\nHxGDaXsQmJ+2FwFnMvXOAItHKT+byq1FVXqnP9adv1f/MmseUx5QFhEhqaq38L29vcPbhUKBQqFQ\nzY+3KhhrYriR6/x63V+z6isWixSLxap93lSahgoRMSBpIXAwNQ1tBoiIp1O9vcBTlJqGDmaahh6i\n1LTkpqEW5bl8zJpHo5qGdgEb0vYG4NVM+XpJMyUtAdqBQxExAFyStColjx/J7GMtyElcs+lj3CcC\nSS8Bq4G5lPIB/wH4r0AfcBtwCngwIi6m+l8FvgBcAR6PiNdT+QpgOzAL2B0Rj43xfX4iqLFqD9Ly\noC+zxvKAMpuwyQzSKnex96Avs8by7KM2YdmePLNmzaJQKAxf4LMjfufNm8fp06eZPXs2ly5d4s03\n3wQ+ONOnB32ZtTY/EeRQtg//2rVrx+z3P3fuXM6fPw/AggULGBgYmNA8QWZWH41KFlsLy/bhL9fv\nf/ny5cPbb7311pjJYY8JMGttfiLIibHa+EfezWdfD+3nO32z5uZksQ1zQtcsn5wstmHZ0b533XXX\nNev5OqFrZmNxIJhGyq3n66kezGwsbhpqMeWaf7Lt+w8//LCngDDLCecIciB78c/25+/u7h5e5GW8\nJLCZTV8OBC2k0qkYRtbL9vUf2Z9/5DgAJ4HN8sfJ4hYy1tTNQ69Hu+vv6em5pu3/lVde4Yknnhi+\n03cS2MymLCKa6q90SNPT5z73uQBi5cqVceHChWveW716dQABxIIFC66pd+HCheju7v7APhFR9j0z\ny4d03Zz0dddNQ3U0st0++xRw+fJl9u/fP+pdv5lZOc4RNIGRbfpjTdxWbpDXmjVrmDlzpi/+ZjZh\nzhE0SLk2/bEmbis3a+f27dsdAMysIer+RCCpE3gWuA74WkQ8M+L9hj4RZC/wI+/ms3f62Yv/yJ48\n2T78bW1tw00+nrXTzGphqk8E9U4EXwecBG4HZgCHgWUj6lQpfTI52aTt3Llzh7e7u7vHTOieOnXq\nmoRtNoE72WTuwYMHa/DrWpPPxVU+F1f5XFzFFJPF9Z6G+m7gZESciojLwH8B1tTji3t6eigUCnR1\ndbFhw4bh7aG78qHXM2bMAD44DfPIKZqz0zJ/7GMfu2Ya5uy0zJOdorlYLFbvx7c4n4urfC6u8rmo\nnnrnCBYDP8y8PgOsmuiHjNV8U2lTzsh2+2yb/po1a+ju7h51GuaR8/V48JaZTQf1DgQVNf53dXWV\nvcBnB2ZlL+rlLvALFiwA+EC7/dC8PEPvjUzaZi/2vvib2XRU12SxpHuA3ojoTK+3AO9HJmEsqbX6\njpqZNYFolXEEkq4H/hz458CPgEPAQxHxg7odhJmZXaOuTUMRcUXSrwGvU+pB9HUHATOzxmq6kcVm\nZlZf9e4+OiZJnZKOSToh6SuNPp56knSrpIOS3pX0fUmPpfI5kvolHZe0T1JuRp1Juk7SO5JeS69z\neS4ktUl6RdIPJB2VtCrH52JL+j9yRNJOSTfk5VxIekHSoKQjmbIxf3s6VyfSNfX+8T6/KQKBpOuA\n3wU6gQ7gIUnLGntUdXUZ+PWI+ARwD/Cr6fdvBvojYilwIL3Oi8eBo1ztaZbXc/EcsDsilgGfAo6R\nw3Mh6XbgS8BdEfFJSk3L68nPufgGpetj1qi/XVIHsI7StbQTeF5S2Wt9UwQCGjjQrBlExEBEHE7b\n/wf4AaUxFw8AO1K1HcDaxhxhfUm6BegCvgYM9YTI3bmQ9FHgsxHxApRybBHxHjk8F8AlSjdMs1On\nk9mUOpzk4lxExP8ALowoHuu3rwFeiojLEXGK0mwOd5f7/GYJBKMNNFvcoGNpqHTncyfwNjA/IgbT\nW4PA/AYdVr39NvAE8H6mLI/nYgnwY0nfkPQnkn5P0o3k8FxExF8DvwX8JaUAcDEi+snhucgY67cv\nonQNHTLu9bRZAoEz1oCkjwB/ADweET/Nvjc0n0hDDqyOJH0eOBcR73D1aeAaeTkXlHr13QU8HxF3\nAX/DiKaPvJwLSR8HvkxpnrJFwEck/XK2Tl7OxWgq+O1lz0uzBIKzwK2Z17dybUSb9iTNoBQEvhkR\nr6biQUkL0vsLgXONOr46+nngAUl/AbwE/IKkb5LPc3EGOBMR302vX6EUGAZyeC5WAv8zIn4SEVeA\nPwT+Cfk8F0PG+j8x8np6SyobU7MEgu8B7ZJulzSTUqJjV4OPqW4kCfg6cDQins28tQvYkLY3AK+O\n3He6iYivRsStEbGEUjLwOxHxCPk8FwPADyUtTUX3Ae8Cr5Gzc0EpSX6PpFnp/8t9lDoT5PFcDBnr\n/8QuYL2kmZKWAO2UBu+ObSpTl1bzD/gcpVHHJ4EtjT6eOv/2z1BqDz8MvJP+OoE5wH7gOLAPaGv0\nsdb5vKwGdqXtXJ4L4NPAd4E/pXQX/NEcn4snKQXCI5SSozPyci4oPR3/CPh/lPKpv1LutwNfTdfS\nY8C/GO/zPaDMzCznmqVpyMzMGsSBwMws5xwIzMxyzoHAzCznHAjMzHLOgcDMLOccCMzMcs6BwMws\n5/4//EExNwSlGnUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10b4b48d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pl.clf()\n",
    "x = np.arange(100)\n",
    "y = np.array(exper_analysis(100))\n",
    "pl.plot(x, y, 'k.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}