cs110_pcw_5_2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Evan\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "1a4c3cfc3c34bf644ee45d91835b6f70",
     "grade": false,
     "grade_id": "cell-61b183447ded09ef",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 5.2\n",
    "\n",
    "## Question 1.\n",
    "Using Figure 7.1 in Cormen et al. as a model, perform manually the partition process on the following list: A = [1,5,6,2,3,8,9,4,7]. You just need to specify the followings:\n",
    "1. The array after the process is done.\n",
    "2. The value of $i$ after the process is done."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "06dce98d07f8f042785a795b32e7ef75",
     "grade": true,
     "grade_id": "cell-7aa520f8af13679b",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    " A = [1,5,6,2,3,8,9,4,7]\n",
    " \n",
    " A = [1,5,6,2,3,4,9,8,7]\n",
    " \n",
    "  A = [1,5,6,2,3,4,7,9,8]\n",
    "  \n",
    "  i = 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "21059776e9083caf84e8abb5b6fb893e",
     "grade": false,
     "grade_id": "cell-6c0a9dfd6980c336",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2.\n",
    "Code up a Python implementation of `partition(A, p, r)`, closely follow the pseudo-code in Cormen et al., p.172. Your function should return the index of the pivot in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "395997ac94ed1416c67b22f7977c07a5",
     "grade": false,
     "grade_id": "cell-1ceb2600756c60ff",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def partition(A,p,r):\n",
    "    \"\"\"\n",
    "    Assume r<len(A) and p>=0\n",
    "    \"\"\"\n",
    "    if r-p == 0:\n",
    "        return 0\n",
    "    x = A[r]\n",
    "    i=p-1\n",
    "    for j in range(p,r):\n",
    "        if A[j]<= x:\n",
    "            i+=1\n",
    "            A[i],A[j]=A[j],A[i]     \n",
    "    A[i+1],A[r]=A[r],A[i+1]\n",
    "    return i+1\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "34aa315313b6f9d8de8efe0922e5b563",
     "grade": true,
     "grade_id": "cell-a57b60117a7b82fb",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = [1,5,6,2,3,8,9,4,7]\n",
    "assert(partition(A, 0, len(A)-1)==6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "3496e310776eba92a8290d114db627cd",
     "grade": false,
     "grade_id": "cell-cd490c45f6733522",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3.\n",
    "\n",
    "Code up your own Python implementation of `quicksort(A, p, r)`, using `partition(A,p,r)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "7e40c51fd1bd31c790aa0dd8abde1fb7",
     "grade": false,
     "grade_id": "cell-8c39ebb8cd1aa83a",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def quick_sort(A,p,r):\n",
    "    # YOUR CODE HERE\n",
    "    if p < r:\n",
    "        q = partition(A,p,r)\n",
    "        quick_sort(A,p,q-1)\n",
    "        quick_sort(A,q+1,r)\n",
    "    return A\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "80923d1142f0ef958a616db1105a8c1a",
     "grade": true,
     "grade_id": "cell-4f822430efd456ee",
     "locked": true,
     "points": 1,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "A = [0]\n",
    "assert(quick_sort(A, 0, 0) == [0])\n",
    "A = [3,1,2]\n",
    "assert(quick_sort(A, 0, 2) == [1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "741cfe874ccaef343713f81ec963360c",
     "grade": false,
     "grade_id": "cell-53941fba9302c591",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 4. \n",
    "Explain (using experimental plots) the running time of `quick_sort` when: \n",
    "1. all elements of array A have the same value (e.g., [1,1,1])?\n",
    "2. array A contains distinct elements sorted in decreasing order (e.g., [5,4,2,1])?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f5ddaf0e684d72d229df078b18f321f8",
     "grade": true,
     "grade_id": "cell-b58035dd5fa02329",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import time\n",
    "\n",
    "def timer_function(input_array):\n",
    "    start_time = time.time()\n",
    "    quick_sort(input_array,input_array[0],input_array[len(input_array)-1])\n",
    "    stop_time = time.time()     \n",
    "    return stop_time - start_time\n",
    "\n",
    "\n",
    "\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZYAAAD4CAYAAADPccAIAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3deXxV9b3v/9eHhBkECeDAYBJEGQRBAyh6KpUWsBXxFnoYei326NEex0PvbSs9t73Wn63Dz1NrKw4c663aeiIHr4ralh4rrcNhCooDIAUCQhxKIICEKdPn/rFW4k7Ye2cnJNlD3s/HI4/s/d3f9f2utXfYb75r+C5zd0RERFpKh2SvgIiIZBYFi4iItCgFi4iItCgFi4iItCgFi4iItKjsZK9AMvTt29dzc3OTvRoiImll3bp1e9y9X2P12mWw5ObmUlRUlOzVEBFJK2b2YSL1tCtMRERalIJFRERalIJFRERaVLs8xhJNZWUlJSUlHD16NNmrIknSpUsXBg4cSMeOHZO9KiJpTcESKikpoWfPnuTm5mJmyV4daWPuzt69eykpKSEvLy/ZqyOS1rQrLHT06FFycnIUKu2UmZGTk6MRq0gLULBEUKi0b/r8RVqGdoWJiGS4mhpn898Osqp4L/17duGro09r1f40YkkhP/nJTxg5ciSjR49mzJgxrF69uk36vf3221m4cGG9svXr1zN8+PC4y02aNEkXmoqkoJoaZ9Mnn/F/3tzO9U8Vcd6d/8llD7zOj1/cyB82fNrq/WvEkiJWrlzJSy+9xFtvvUXnzp3Zs2cPFRUVbdL33Llzueyyy7jrrrvqygoLC5k3b16b9C8iJyZyRLKqeC+rt5ex/3AlAIP7dGPKiFO4ID+HCfk5DOjdtdXXR8GSIj755BP69u1L586dAejbt2/da3fccQcvvvgiR44cYeLEiTz66KOYGZMmTWLs2LGsW7eO0tJSnnzySe666y7ee+89Zs+ezZ133gnAb37zG37xi19QUVHBhAkTeOihh8jKyqpr/+yzz6Z3796sXr2aCRMmALBkyRKWL18OwD/90z+xdu1ajhw5wqxZs/jxj3983Pr36NGD8vJyAJYuXcpLL73Er3/9a0pLS/n2t7/Nzp07Afj5z3/ORRdd1ArvoEj7kWpB0lBCwWJm04AHgCzgMXe/u8HrnYEngfOBvcBsd98RvrYQuAaoBm5x9+Xx2jSzPKAQ6AO8BVzl7hWN9DEaeBQ4CagBxrl7s0/v+fGLG9j48WfNXTyqEaefxP+ePjLm61OmTOGOO+7grLPO4ktf+hKzZ8/mkksuAeCmm27iRz/6EQBXXXUVL730EtOnTwegU6dOvPbaazzwwAPMmDGDdevW0adPH4YMGcKCBQvYvXs3zzzzDG+++SYdO3bkhhtu4Le//S3f/OY36/U/d+5cCgsLmTBhAqtWrSInJ4ehQ4cCwS66Pn36UF1dzeTJk3n33XcZPXp0Qtt96623smDBAi6++GJ27tzJ1KlT2bRpU5PfP5H2rKbG+eDTz4NkzY7UCpKGGg0WM8sCFgFfBkqAtWa2zN03RlS7Btjn7mea2RzgHmC2mY0A5gAjgdOBV8zsrHCZWG3eA9zv7oVm9kjY9sNx+sgGfkMQQO+YWQ5QeULvShL06NGDdevW8frrr7NixQpmz57N3XffzdVXX82KFSu49957OXz4MGVlZYwcObIuWK644goARo0axciRIznttOCgXH5+Prt27eKNN95g3bp1jBs3DoAjR47Qv3//4/qfM2cOEydO5F//9V8pLCxk7ty5da8tWbKExYsXU1VVxSeffMLGjRsTDpZXXnmFjRs//1P57LPPOHjwID179mzeGyXSDqRbkDSUyIhlPLDV3YsBzKwQmAFEBssM4Pbw8VLgQQvO3ZwBFLr7MWC7mW0N2yNam2a2CbgUqN25/0TY7sNx+pgCvOvu7wC4+95ENz6WeCOL1pSVlcWkSZOYNGkSo0aN4oknnmDOnDnccMMNFBUVMWjQIG6//fZ611rU7jrr0KFD3ePa51VVVbg78+fPr3f8JJpBgwaRm5vLX/7yF5599llWrlwJwPbt27nvvvtYu3YtJ598MldffXXUaz0iT9WNfL2mpoaVK1fStWvq/fGLpIp0D5KGEgmWAcCuiOclwIRYddy9yswOADlh+aoGyw4IH0drMwfY7+5VUerH6uMswM1sOdCPIMjuTWC7UsrmzZvp0KFD3e6n9evXc8YZZ9R9Sfft25fy8nKWLl3KrFmzEm538uTJzJgxgwULFtC/f3/Kyso4ePAgZ5xxxnF1586dy4IFCxgyZAgDBw4EghFG9+7d6dWrF3/729/4/e9/z6RJk45b9pRTTmHTpk2cffbZPPfcc3UjkilTpvDggw/y3e9+t267xowZ06T3RiTTNAyS1dvLOHAkCJIzcroxdcSpXDCkDxPycjg9DYKkoUSCJdpVY55gnVjl0U5zjlc/Xh/ZwMXAOOAw8CczW+fuf6q3gmbXAdcBDB48OEpTyVVeXs7NN9/M/v37yc7O5swzz2Tx4sX07t2bf/zHf2TUqFHk5ubW7dJK1IgRI7jzzjuZMmUKNTU1dOzYkUWLFkUNlq9//evceuut/PKXv6wrO/fccxk7diwjR44kPz8/5oH3u+++m8svv5xBgwZxzjnn1B3I/8UvfsGNN97I6NGjqaqq4gtf+AKPPPJIk7ZBJN01FiTTRqZ3kDRk7g0zokEFswuB2919avh8IYC73xVRZ3lYZ2V4zONTgtHDbZF1a+uFix3XJnA3UAqcGo5K6vqO08dsYJq7Xx229UPgqLv//7G2qaCgwBtef7Fp06ZGr9uQzKe/A2kJNTXOpk8/Y1VxWbBrq0GQXJCXk5ZBEv6nvaCxeomMWNYCQ8OztT4iOBjf8AKHZcB8YCUwC3jV3d3MlgFPm9nPCA7eDwXWEIw+jmszXGZF2EZh2OYLjfSxHPiemXUDKoBLgPsT2C4RkRbRWJBk2oikMY0GSzhyuAlYTnBq8OPuvsHM7gCK3H0Z8CvgqfDgfBlBUBDWW0JwoL8KuNHdqwGitRl2+X2g0MzuBN4O2yZOH/vC4FpLsGvsd+7+8gm9KyIicShI4mt0V1gm0q4wiUV/BxJNvCDJzenGBfk54VlbfTitV+YGSUvuChMRaVcaC5LLzjm1XQRJcylYRKTdqw4nbQzO2ipjzfa9fHY0uOpBQdJ0ChYRaXcaC5KvjDpNQXICFCwpJCsri1GjRlFZWUl2djbz58/nn//5n+nQIXXubjBx4kT+67/+64TaOHToEIMHD6a4uJhevXrVlV955ZXMmzePv//7v4+63J///Gfuu+8+XnrppRPqX9qfeEGS17c7Xx0dBkleDqf26pLktU1/CpYU0rVrV9avXw/A7t27mTdvHgcOHIg6m3BTVFVVkZ3dMh/1iYYKQPfu3ZkyZQrPP/888+fPB+DAgQO88cYbPP300yfcvoiCJLlS57/CUk///v1ZvHgxDz74IO5OdXU13/3udxk3bhyjR4/m0Ucfrat77733MmrUKM4991xuu+02ILgJ1w9+8AMuueQSHnjgAUpLS5k5cybjxo1j3LhxvPnmmwCsWbOGiRMnMnbsWCZOnMjmzZsB2LBhA+PHj2fMmDGMHj2aLVu2AMFkmRCMHiZNmsSsWbMYNmwY3/jGN6g9w/B3v/sdw4YN4+KLL+aWW27h8ssvP277amdTrvXcc88xbdo0unXrFnOdIt1+++3cd999dc/POeccduzYAQS3Cahd9+uvv57q6mqqq6u5+uqrOeeccxg1ahT3369LnTJJdY3z/kcHeOz1Yq59Yi1j7vgjl//yDe58eRPbSsv56ujTeGDOGFYtnMyK/zmJu742mhljBihUWolGLNH8/jb49L2WbfPUUXDZ3Y3Xi5Cfn09NTQ27d+/mhRdeoFevXqxdu5Zjx45x0UUXMWXKFD744AOef/55Vq9eTbdu3SgrK6tbfv/+/fzlL38BYN68eVGnrx82bBivvfYa2dnZvPLKK/zgBz/g2Wef5ZFHHuHWW2/lG9/4BhUVFVRXVx+3fm+//TYbNmzg9NNP56KLLuLNN9+koKCA66+/ntdee428vLx6syRHmjZtGtdeey179+4lJyeHwsJCbr75ZoCY65SITZs2Rb1NwMiRI/noo494//33694bSV/1RyTBFCkHI0Ykl2tEklQKlhRXOwr44x//yLvvvsvSpUuBYNfRli1beOWVV/jWt75Ft27dAOjTp0/dsrNnz657HGv6+gMHDjB//ny2bNmCmVFZGZxSeeGFF/KTn/yEkpISvva1r9VNjhlp/PjxdZNVjhkzhh07dtCjRw/y8/PJy8sDgpHJ4sWLj1u2U6dOXHHFFSxdupSZM2eyfv16pkyZUrdt0dYpEX/605+i3iZg+vTpFBcXc/PNN/PVr361ri9JDwqS9KJgiaaJI4vWUlxcTFZWFv3798fd+eUvf8nUqVPr1fnDH/5Qb8r6SN27d697HGv6+ptvvpkvfvGLPPfcc+zYsaNu5uJ58+YxYcIEXn75ZaZOncpjjz3GpZdeWm/ZyGn6s7Ky6qbpT9TcuXO58847cXdmzJhBx44dAfjhD38YdZ0iZWdnU1NTU/e8dhboeLcJeOedd1i+fDmLFi1iyZIlPP744wmvq7SteEGS37c7l48+nQvy+3BBfg6nnKQgSTUKlhRVe0vfm266CTNj6tSpPPzww1x66aV07NiRv/71rwwYMKDuzpPz5s2r2xUWOWqpFWv6+gMHDjBgQHBngl//+td19YuLi8nPz+eWW26huLiYd99997hgiWbYsGEUFxezY8cOcnNzeeaZZ2LW/eIXv8j8+fNZtGhRvRmVY61TpNzc3Lqzw9566y22b98OxL5NQPfu3enUqRMzZ85kyJAhXH311Y1ui7QdBUlmUbCkkCNHjjBmzJi6042vuuoqvvOd7wBw7bXXsmPHDs477zzcnX79+vH8888zbdo01q9fT0FBAZ06deIrX/kKP/3pT49rO9b09d/73veYP38+P/vZz+oFxzPPPMNvfvMbOnbsyKmnnlp3a+TGdO3alYceeohp06bRt29fxo8fH7Nuhw4dmDlzJv/xH//BF77whbryWOsUaebMmTz55JOMGTOGcePGcdZZwY1JY90moGvXrnzrW9+qG+U0duMzaV3VNc7Gjz+rd2MrBUnm0FxhIc0R1XLKy8vp0aMH7s6NN97I0KFDWbBgQbJXKyH6O2gdjQXJhPwcBUka0FxhkjT/9m//xhNPPEFFRQVjx47l+uuvT/YqSRs7Lki2l3HwmEYk7YWCRVrcggUL0maEIi0jbpD06870MacHMwDn9aG/giTjKVgiuHvMM6wk87XH3cLNpSCReBQsoS5dutRdrKdwaX/cnb1799Kli74Eo6mqrmFjxBQpaxUkEoeCJTRw4EBKSkooLS1N9qpIknTp0qXugs/2TkEiJ0LBEurYsWPd1eIi7U28IBnSrztXhEEyQUEiCVCwiLRDCQdJfh/691SQSNMoWETagarqGjZEHGxfu2Mf5QoSaSUKFpEM1FiQzFCQSCtSsIhkAAWJpBIFi0gaihckZ/bvwZVjgyAZn6cgkbaXULCY2TTgASALeMzd727wemfgSeB8YC8w2913hK8tBK4BqoFb3H15vDbNLA8oBPoAbwFXuXtFrD7MLBfYBNTeZnCVu3+7ye+ESApTkEg6aTRYzCwLWAR8GSgB1prZMnffGFHtGmCfu59pZnOAe4DZZjYCmAOMBE4HXjGzs8JlYrV5D3C/uxea2SNh2w/H6iNsa5u7jzmB90EkpVRV1/B+RJAUxQiSCXk59OvZuZHWRNpWIiOW8cBWdy8GMLNCYAYQGSwzgNvDx0uBBy24fH0GUOjux4DtZrY1bI9obZrZJuBSYF5Y54mw3Yfj9CGS9hQkkkkSCZYBwK6I5yXAhFh13L3KzA4AOWH5qgbLDggfR2szB9jv7lVR6sfqAyDPzN4GPgP+l7u/3nAjzOw64DqAwYMHN77VIq2oYZCs3V7GoYpqQEEi6S+RYIk2Kmg4W1+sOrHKOzSxfrw+PgEGu/teMzsfeN7MRrr7Z/Uqui8GFkNwP5YobYm0mnhBMrR/D7523sC6YyQKEkl3iQRLCTAo4vlA4OMYdUrMLBvoBZQ1smy08j1AbzPLDkctkfWj9uHBlLTHANx9nZltA84C6t/JS6QNVVXX8N5HB1hVXBbu2lKQSPuRSLCsBYaGZ2t9RHAwfl6DOsuA+cBKYBbwqru7mS0DnjaznxEcvB8KrCEYfRzXZrjMirCNwrDNFxrpox9BwFSbWX7YR3Ez3guRZlOQiHyu0WAJj2fcBCwnODX4cXffYGZ3AEXuvgz4FfBUeHC+jCAoCOstITjQXwXc6O7VANHaDLv8PlBoZncCb4dtE6sP4AvAHWZWRXBK87fdvaz5b4lI4yqra3hfQSISle55L5KAxoLkgvycuivb+/ZQkEhm0j3vRU5AvCA565QezDz/8xGJgkSkPgWLCEGQBMdIgmnki3aUcVhBItIsChZplxoLklkKEpFmU7BIu6AgEWk7ChbJSAoSkeRRsEhGqKyu4d2SA3VXtq/7cF9dkJx9Sk++HhEkOQoSkValYJG0pCARSV0KFkkLChKR9KFgkZSkIBFJXwoWSQkNg6Roxz6OVCpIRNKRgkWSoqKqhvc+2h9xZfvnQTLs1J7MHjeIC/L7MD4vhz7dOyV5bUWkKRQs0iYUJCLth4JFWoWCRKT9UrBIi1CQiEgtBYs0S0VVDe+W7P/8yvYPyzhaWQMoSETaOwWLJKSxIJkzbnDdWVsKEpH2TcEiUSlIRKS5FCwCJB4kE/L6cLKCRETiULC0UwoSEWktCpZ2oqKqhndK9rNq215WbQ+mSFGQiEhrULBkqGNV1cEUKVGCZPhpJzF3fHiMJFdBIiItS8GSIRQkIpIqFCxpSkEiIqkqoWAxs2nAA0AW8Ji7393g9c7Ak8D5wF5gtrvvCF9bCFwDVAO3uPvyeG2aWR5QCPQB3gKucveKeH2Eyw0GNgK3u/t9TX4nUly8YyQKEhFJJY0Gi5llAYuALwMlwFozW+buGyOqXQPsc/czzWwOcA8w28xGAHOAkcDpwCtmdla4TKw27wHud/dCM3skbPvhWH1ErMP9wO+b9zakvht+u45XNu3GDIadqiARkdSVyIhlPLDV3YsBzKwQmEEwOqg1A7g9fLwUeNDMLCwvdPdjwHYz2xq2R7Q2zWwTcCkwL6zzRNjuw7H6cHc3syuBYuBQ4pueXt7euZ8pI07h3lmj6d1NQSIiqatDAnUGALsinpeEZVHruHsVcADIibNsrPIcYH/YRsO+ovZhZt2B7wM/jrcRZnadmRWZWVFpaWkjm5xa9h+uYO+hCgpyT1aoiEjKSyRYLEqZJ1inpcrj9fFjgl1n5VFe/7yi+2J3L3D3gn79+sWrmnK2lQYDsSH9eiR5TUREGpfIrrASYFDE84HAxzHqlJhZNtALKGtk2Wjle4DeZpYdjkoi68fqYwIwy8zuBXoDNWZ21N0fTGDb0kJxaZCZ+QoWEUkDiYxY1gJDzSzPzDoRHIxf1qDOMmB++HgW8Kq7e1g+x8w6h2d7DQXWxGozXGZF2AZhmy/E68Pd/87dc909F/g58NNMChUIRiwds4xBJ3dN9qqIiDSq0RGLu1eZ2U3AcoJTgx939w1mdgdQ5O7LgF8BT4UH58sIgoKw3hKCA/1VwI3uXg0Qrc2wy+8DhWZ2J/B22Dax+mgPikvLOSOnO9lZifw/QEQkuSwYJLQvBQUFXlRUlOzVSNjkf/0zQ/r1YPE3C5K9KiLSjpnZOndv9ItI/wVOcVXVNewsO8yQ/jq+IiLpQcGS4nbtO0JltZPft3uyV0VEJCEKlhS3bXdwRphGLCKSLhQsKa54TxgsfRUsIpIeFCwpbtvuQ/Tt0Yle3Tome1VERBKiYElxxXvKyddoRUTSiIIlxRWXHiK/nw7ci0j6ULCksNrJJzVHmIikEwVLCqudfFIjFhFJJwqWFLYtnHxSIxYRSScKlhRWHE4+OVCTT4pIGlGwpDBNPiki6UjfWClsW2k5Q3R8RUTSjIIlRVWGk0/q5l4ikm4ULClqV9lhKqtdB+5FJO0oWFJUsU41FpE0pWBJUXWnGms6FxFJMwqWFFVcqsknRSQ9KVhSlCafFJF0pWBJUdtKDzGkv46viEj6UbCkoH2HKig7VKERi4ikJQVLCqq7a6RGLCKShhQsKahuVmONWEQkDSUULGY2zcw2m9lWM7styuudzeyZ8PXVZpYb8drCsHyzmU1trE0zywvb2BK22SleH2Y23szWhz/vmNl/a+6bkSo0+aSIpLNGg8XMsoBFwGXACGCumY1oUO0aYJ+7nwncD9wTLjsCmAOMBKYBD5lZViNt3gPc7+5DgX1h2zH7AN4HCtx9TNjHo2aW3bS3IbVsKy0nV5NPikiaSuSbazyw1d2L3b0CKARmNKgzA3gifLwUmGxmFpYXuvsxd98ObA3bi9pmuMylYRuEbV4Zrw93P+zuVWF5F8AT3fhUVVxarivuRSRtJRIsA4BdEc9LwrKodcIv+QNATpxlY5XnAPsjgiKyr1h9YGYTzGwD8B7w7Yjl65jZdWZWZGZFpaWlCWx2clRW1/Dh3sOaI0xE0lYiwWJRyhqOCmLVaanyuOvh7qvdfSQwDlhoZl2Oq+i+2N0L3L2gX79+UZpKDbvKDlNV45rVWETSViLBUgIMing+EPg4Vp3w+EYvoCzOsrHK9wC9I46RRPYVq4867r4JOASck8B2pSRNPiki6S6RYFkLDA3P1upEcDB+WYM6y4D54eNZwKvu7mH5nPCMrjxgKLAmVpvhMivCNgjbfCFeH2Eb2QBmdgZwNrAj4XcgxWjySRFJd42ePeXuVWZ2E7AcyAIed/cNZnYHUOTuy4BfAU+Z2VaCUcSccNkNZrYE2AhUATe6ezVAtDbDLr8PFJrZncDbYdvE6gO4GLjNzCqBGuAGd9/T/LckuTT5pIikOwsGCe1LQUGBFxUVJXs1opr18H/RoYOx5PoLk70qIiL1mNk6dy9orJ4ulEgxxXsO6T73IpLWFCwpRJNPikgmULCkEE0+KSKZQMGSQjT5pIhkAgVLCtlWWk6nrA6afFJE0pqCJYUUlx7ijJxumnxSRNKavsFSyLbScs0RJiJpT8GSIiqra9i597CmchGRtKdgSRGafFJEMoWCJUXUnhGmiyNFJN0pWFJEcTj5pEYsIpLuFCwpYltpOX17dKZXV00+KSLpTcGSIopLD+nAvYhkBAVLighONVawiEj6U7CkgH2HKth3uFLXsIhIRlCwpIDaySe1K0xEMoGCJQVs2117qrFGLCKS/hQsKWDbntrJJ7sle1VERE6YgiUFbNt9iNy+3cjqYMleFRGRE6ZgSQHFe8p1DxYRyRgKliTT5JMikmkULEm2M5x8UgfuRSRTKFiSrLj2dsQasYhIhkgoWMxsmpltNrOtZnZblNc7m9kz4eurzSw34rWFYflmM5vaWJtmlhe2sSVss1O8Pszsy2a2zszeC39f2tw3Ixm2afJJEckwjQaLmWUBi4DLgBHAXDMb0aDaNcA+dz8TuB+4J1x2BDAHGAlMAx4ys6xG2rwHuN/dhwL7wrZj9gHsAaa7+yhgPvBU096C5CrW5JMikmESGbGMB7a6e7G7VwCFwIwGdWYAT4SPlwKTzczC8kJ3P+bu24GtYXtR2wyXuTRsg7DNK+P14e5vu/vHYfkGoIuZdU70DUg2TT4pIpkmkWAZAOyKeF4SlkWt4+5VwAEgJ86yscpzgP1hGw37itVHpJnA2+5+rOFGmNl1ZlZkZkWlpaWNbHLb0X3uRSTTJBIs0a7a8wTrtFR5o+thZiMJdo9dH6Ue7r7Y3QvcvaBfv37RqrS5srrJJzViEZHMkUiwlACDIp4PBD6OVcfMsoFeQFmcZWOV7wF6h2007CtWH5jZQOA54Jvuvi2BbUoJtXeN1IhFRDJJIsGyFhganq3VieBg/LIGdZYRHDgHmAW86u4els8Jz+jKA4YCa2K1GS6zImyDsM0X4vVhZr2Bl4GF7v5mUzY+2XSqsYhkokaDJTyecROwHNgELHH3DWZ2h5ldEVb7FZBjZluB7wC3hctuAJYAG4E/ADe6e3WsNsO2vg98J2wrJ2w7Zh9hO2cCPzSz9eFP/2a+H21qW6kmnxSRzGPBIKF9KSgo8KKiomSvBtc+UcTOskP8ccElyV4VEZFGmdk6dy9orJ6uvE8iTT4pIplIwZIktZNPDumv4ysiklkULElSO/mkRiwikmkULE1QXeMcPFpJZXXNCbe1bXd4qnF/BYuIZBYFSxO8/9EBRt3+R17fcuJX7hfv0anGIpKZFCxJUjv55EldNPmkiGQWBUuSbCs9pKlcRCQjKViSpLi0XPdgEZGMpGBJAk0+KSKZTMGSBJp8UkQymYIlCTT5pIhkMgVLM5zo9GqafFJEMpmCpQks2q3GmmFb6SFy+3Yjq0MLNSgikkIULElQrNsRi0gGU7C0scrqGnaWHdbxFRHJWAqWNvbhXk0+KSKZTcHSxupONdbkkyKSoRQsbUyTT4pIplOwtLFtu8vp11OTT4pI5lKwNEFVTXABy62F63lo+Tvw5JVQurlJbRTvOUR+X41WRCRzKVia4NMDRwEoP1bFu++ug+IVsO7XTWpjW2m5jq+ISEZTsDRBdU3EJfeVR4Lfm15M+FL8skMV7D9cqRGLiGQ0BUsT1EQESIeqw8GDA7vgk/UJLa/JJ0WkPUgoWMxsmpltNrOtZnZblNc7m9kz4eurzSw34rWFYflmM5vaWJtmlhe2sSVss1O8Pswsx8xWmFm5mT3Y3DciEZEjlg6VRz9/YdOLCS2/TcEiIu1Ao8FiZlnAIuAyYAQw18xGNKh2DbDP3c8E7gfuCZcdAcwBRgLTgIfMLKuRNu8B7nf3ocC+sO2YfQBHgR8C/7OJ295k9YKlOtwV1mtQwsFSXHqITtkdGHBy19ZYPRGRlJDIiGU8sNXdi929AigEZjSoMwN4Iny8FJhsZhaWF7r7MXffDmwN24vaZrjMpWEbhG1eGa8Pdz/k7m8QBL7GUBoAAA+sSURBVEyritwV1tUqggejvg57/prQ2WHbSsvJy+muySdFJKMlEiwDgF0Rz0vCsqh13L0KOADkxFk2VnkOsD9so2FfsfpIiJldZ2ZFZlZUWlqa6GL12zhWzgTbRG8O0q02x0Z9Pfi9aVmjyxeXHtKFkRJbdSV8vB4+Whf8R+XAR3D0ANRUJ3vNRJokO4E60f573fA0qFh1YpVHC7R49RNdj5jcfTGwGKCgoKBZd1QZ3ulTnun8//Gtiu/SlXDE0icfBo4Pdod94bsxly07VMGHZYe5fPRpzelaMlF1JXzyDux4HXa8ATtXQUV59LrZXaFzD+jUI/zdEzp1jyjrGfyuK+sZ/u4e8bjH5787ZLXttkq7kkiwlACDIp4PBD6OUafEzLKBXkBZI8tGK98D9Daz7HBUElk/Vh9t5uxTe9Y97mLHcOuAZXeG4dPhP38I+z6Ek8+Iuuyz60qornEuP/f0tlpdSTXxgqTfMDh3Dgy+MPjirygPfo7V/j4Ylh36vOxQKezbXr8s0f9rRQZVZODELOsZI7TCUFNQSYREgmUtMNTM8oCPCA7Gz2tQZxkwH1gJzAJedXc3s2XA02b2M+B0YCiwhmD0cVyb4TIrwjYKwzZfiNdH8za7eSxi0NSNY9RkdyXLDIZfHgTLBy/BhTcet5y78+9rdlJwxsmcdUrP416XDJVIkOReDGdcBD36n3h/NTVQeTgImsgwqg2d44LqUP2yw3tg3476ZU0OqmgjpAZlnbp/PsKKNvrq1AOyEvlqklTV6Kfn7lVmdhOwHMgCHnf3DWZ2B1Dk7suAXwFPmdlWglHEnHDZDWa2BNgIVAE3uns1QLQ2wy6/DxSa2Z3A22HbxOojbGsHcBLQycyuBKa4+8bmvimxRN5BsisV1GR1IQuC3WGnjAp2h0UJllXFZRTvOcSNXzyzpVdJUkntMZLIIKkMJh1tlSBpqEOH4Mu5cw/glBNvr6YGqo7EGDVFhtYhqDgYUa8lgqpL/eCpN0KKMWqKGloKqmRI6N12998Bv2tQ9qOIx0eBr8dY9ifATxJpMywvJjhrrGF5vD5y425AK+hix6jK6krdVJLDp8Of74KDf4Oe9f9RP71mJyd1yearOr6SWRoLkjFzWzdIWluHDuEXd3daJKjcgxFVzBFU5K6+iKCqDbLDe4PdzZFlzQ2qesenou3+6xkjtMLlFVRx6d1pgshdYV2poCor4nqU4dPhzz+FzS9DwT/UFe8tP8by9z9l3oTBdOmo/dBpLW6QDIcx8yKCpF9y1zUVmbVxUEXu6jsYMboq/zyo9u+sv0xTgyrWCCnh0MrMoMqsrWllkaeldeMYVR26fF7Qfzj0GRLsDosIlmffKqGiuoZ5Ewa33YpKy1CQpLbWCqrjdvU1DK0YQXa4rH5QVZSD1yTWd3aX+COkmMenYgRZVnJvy6FgaYJ6x1jsGBUdetR/cfh0WPkgHNkHXU8OD9rv0kH7dKEgad8ig6oldl26B5PVJrqrr2FoHdkXzEUYeRwr0aDK6hx7hHTGxTDhuhPfvjgULE0QGSxdqKDCOtevMPwKePPn8NflcO4cVhbvZfueQ9x8qQ7ap6TqSvj47YggWa0gkZZjBp26BT+tElSN7OprGGS1QdWz9S95ULA0U1eOccy61C88fSycNCDYHXbuHP59zS56de3IV0bpoH1KUJBIOmvpoGpFCpZmMJxudowDDUcsHTrAsMvhrSfYW1bGH97/hP9+wRk6aJ8s8YKk/wgY+43Pg6R73+Suq0gGUbA0yef7wrpQwad0Pr7K8Omw5lHeenUpldUDmDdeB+3bzHFBsio4GAsKEpE2pGBppq4c4widjn9h8IV4txzsgxcZl7uQoTpo33oaDZL/riARSQIFSzMYTlcqOOxRRixZ2ew+fTLjt7xI+fmntv3KZbKqivpBsmu1gkQkBSlYmqEzlXQw53BNlBEL8OzhsdxgS/hKj78C+W27cpkkbpCMhLFXRQRJwndQEJFWpmBphtop8w/58cGyt/wYiz4cwDWdu9F5y8swfFpbr176UpCIZAQFSzN0tWMAlNccf3Xr0nUlHKrOpiL/y3T+4GW4/OeaUjwWBYlIRlKwNENXgmA5WF1/xFI7Pf643JPpOfZrsPUF2Lky+HIUBYlIO6FgaYbaXWEHq+uPWFZu28uOvYe5ZfJQOHN0MP/Pphfbb7BUVcDHb9W/jqTqSPCagkQkYylYmqF2V9hnVfWD5ek1Oz+/0r5jFgyZHATLtLvrzweTqeIFySnnwPnzgyAZPFFBIpLBFCzNULsr7LOIEcue8mMs3/Bp/Svth08PptH/+C0YcH4yVrV1KUhEJAoFS1OEo45uYbDsjxixPLuuhMpqr3+l/VlToUN2MGrJhGBJNEjOuAi69UnuuopI0ihYmqF2V9j+qmzcHXfqDtrXu9K+Wx/I/TvYuAwm/+/02x1WVQEfrQtCZMfrsGuNgkREGqVgaYYu4cH7wzWdOFZVw1sf7mPH3sPc+qWhx1cePh1e/g6UfhDcDCyVxQ2SUXD+1WGQTFSQiEhMCpZmqD3GcoTOHKmo5rfhQfvLzokyPf6wr8LL/yPYHZZqwVJ1DD56S0EiIi1KwdIM3ezzYCnZd4Q/bviUqy7IjT49fs9TYdAE2LQMLvleG69pAwoSEWkDCpZm6EoFTgcqyOapVTuCg/YTBsVeYPh0+OO/QNl26JPXdiuqIBGRJFCwNEMXjlGd3RUwnn/7Y8bn9uHM/nGmxx9+eRAsH7wEE29uvRWrOhblGMlRwMKD7VcrSESk1SUULGY2DXgAyAIec/e7G7zeGXgSOB/YC8x29x3hawuBa4Bq4BZ3Xx6vTTPLAwqBPsBbwFXuXtGcPlpLNztGTXZwW+KK6hrmxhutAJycC6eODo6ztGSwxAuSU8+Bgn8IryO5UEEiIm2m0WAxsyxgEfBloARYa2bL3H1jRLVrgH3ufqaZzQHuAWab2QhgDjASOB14xczOCpeJ1eY9wP3uXmhmj4RtP9zUPty9+kTemHi6UoFnBxf8xTxo39DwK2DFnXDw0+C4S3MoSEQkDSQyYhkPbHX3YgAzKwRmAJHBMgO4PXy8FHjQzCwsL3T3Y8B2M9satke0Ns1sE3ApMC+s80TY7sPN6GNlgu9Bk51khznacSAAM88bmNg97YdPD4LlsS9Bp+5N79Qd9n+oIBGRlJdIsAwAdkU8LwEmxKrj7lVmdgDICctXNVh2QPg4Wps5wH53r4pSvzl91DGz64DrAAYPbuZ96PsNY+ugmeRkHaHnqMv4x0/zuPbvEryRV7+z4e/+B+zd2ry+Ac6crCARkZSXSLBEu1zcE6wTq7xDE+s3p4/6Be6LgcUABQUFx72ekI5dOfOax+ue/ktTljWDyT9qVrciIukk2hd8QyVA5NHpgcDHseqYWTbQCyiLs2ys8j1A77CNhn01tQ8REUmCRIJlLTDUzPLMrBPBgfJlDeosA+aHj2cBr7q7h+VzzKxzeLbXUGBNrDbDZVaEbRC2+UIz+xARkSRodFdYeDzjJmA5wanBj7v7BjO7Ayhy92XAr4CnwgPnZQRBQVhvCcGB/irgxtqztaK1GXb5faDQzO4E3g7bpjl9iIhI27PgP/3tS0FBgRcVFSV7NURE0oqZrXP3gsbqJbIrTEREJGEKFhERaVEKFhERaVEKFhERaVHt8uC9mZUCH55AE30JrrlpL9rb9oK2ub3QNjfNGe7er7FK7TJYTpSZFSVyZkSmaG/bC9rm9kLb3Dq0K0xERFqUgkVERFqUgqV5Fid7BdpYe9te0Da3F9rmVqBjLCIi0qI0YhERkRalYBERkRalYGkCM5tmZpvNbKuZ3Zbs9WkKMxtkZivMbJOZbTCzW8PyPmb2n2a2Jfx9clhuZvaLcFvfNbPzItqaH9bfYmbzI8rPN7P3wmV+Ed46OunMLMvM3jazl8LneWa2Olz/Z8JbNxDeeuGZcP1Xm1luRBsLw/LNZjY1ojzl/ibMrLeZLTWzD8LP+8JM/5zNbEH4d/2+mf27mXXJtM/ZzB43s91m9n5EWat/rrH6iMvd9ZPAD8H0/tuAfKAT8A4wItnr1YT1Pw04L3zcE/grMAK4F7gtLL8NuCd8/BXg9wR36LwAWB2W9wGKw98nh49PDl9bA1wYLvN74LJkb3e4Xt8BngZeCp8vAeaEjx8B/il8fAPwSPh4DvBM+HhE+Hl3BvLCv4OsVP2bAJ4Arg0fdwJ6Z/LnTHAr8u1A14jP9+pM+5yBLwDnAe9HlLX65xqrj7jrmux/BOnyE77hyyOeLwQWJnu9TmB7XgC+DGwGTgvLTgM2h48fBeZG1N8cvj4XeDSi/NGw7DTgg4jyevWSuJ0DgT8BlwIvhf9o9gDZDT9XgvsDXRg+zg7rWcPPurZeKv5NACeFX7LWoDxjP2eCYNkVfllmh5/z1Ez8nIFc6gdLq3+usfqI96NdYYmr/eOtVRKWpZ1w6D8WWA2c4u6fAIS/+4fVYm1vvPKSKOXJ9nPge0BN+DwH2O/uVeHzyPWs27bw9QNh/aa+F8mUD5QC/yfc/feYmXUngz9nd/8IuA/YCXxC8LmtI7M/51pt8bnG6iMmBUviou1HTrtztc2sB/As8M/u/lm8qlHKvBnlSWNmlwO73X1dZHGUqt7Ia2mzzQT/Az8PeNjdxwKHCHZfxJL22xzu859BsPvqdKA7cFmUqpn0OTcmqduoYElcCTAo4vlA4OMkrUuzmFlHglD5rbv/37D4b2Z2Wvj6acDusDzW9sYrHxilPJkuAq4wsx1AIcHusJ8Dvc2s9rbcketZt23h670IboPd1PcimUqAEndfHT5fShA0mfw5fwnY7u6l7l4J/F9gIpn9Oddqi881Vh8xKVgStxYYGp5p0ongoN+yJK9TwsIzPH4FbHL3n0W8tAyoPTNkPsGxl9ryb4Znl1wAHAiHwcuBKWZ2cvg/xSkE+58/AQ6a2QVhX9+MaCsp3H2huw9091yCz+tVd/8GsAKYFVZruM2178WssL6H5XPCs4nygKEEBzpT7m/C3T8FdpnZ2WHRZGAjGfw5E+wCu8DMuoXrVLvNGfs5R2iLzzVWH7El86Bbuv0QnGnxV4IzRP4l2evTxHW/mGBo+y6wPvz5CsG+5T8BW8LffcL6BiwKt/U9oCCirX8AtoY/34ooLwDeD5d5kAYHkJO8/ZP4/KywfIIvjK3AfwCdw/Iu4fOt4ev5Ecv/S7hdm4k4CyoV/yaAMUBR+Fk/T3D2T0Z/zsCPgQ/C9XqK4MyujPqcgX8nOIZUSTDCuKYtPtdYfcT70ZQuIiLSorQrTEREWpSCRUREWpSCRUREWpSCRUREWpSCRUREWpSCRUREWpSCRUREWtT/A4nnaghhJtv1AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "A = [1,1,1]    \n",
    "B = [5,4,2,1]\n",
    "\n",
    "A_list = []\n",
    "B_list = []\n",
    "n_list = [1,5,10,50,100,500,1000,5000,10000,50000,100000]\n",
    "for n in n_list:\n",
    "    A = []\n",
    "    B = []\n",
    "    for i in reversed(range(n)):\n",
    "        A.append(1)\n",
    "        B.append(i)\n",
    "    A_list.append(timer_function(A))\n",
    "    B_list.append(timer_function(B))\n",
    "    \n",
    "plt.plot(n_list,A_list)\n",
    "plt.plot(n_list,B_list)\n",
    "plt.legend((\"Same Value\",\"Decreasing Values\"))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}