UABC Unidad 1 - Herramientas de Análisis de Algoritmos.ipynb.ipynb

herramientas-de-an-lisis-de-algoritmos.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "UABC Unidad 1 - Herramientas de Análisis de Algoritmos.ipynb.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/sanchezcarlosjr/3788a69e1144ca9d6105608b08433d1b/herramientas-de-an-lisis-de-algoritmos.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 1 Herramientas de Análisis de Algoritmos\n",
        "## UABC\n",
        "\n",
        "### Ilustración\n",
        "By [Carlos Eduardo Sanchez Torres](https://twitter.com/CharllierJr)\n",
        "\n",
        "[Análisis de algoritmos](https://sanchezcarlosjr.notion.site/An-lisis-de-Algoritmos-38fac5ca34e740719b43673db9f8b9188)"
      ],
      "metadata": {
        "id": "mRIP_0yy7GHb"
      }
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jx85EMoFI6Gb"
      },
      "source": [
        "def merge(sequence, i, compareFunction):\n",
        "    key = sequence[i+1]\n",
        "    print(sequence[:i+1])\n",
        "    while i >= 0 and compareFunction(sequence[i], key):\n",
        "        sequence[i+1] = sequence[i]\n",
        "        i = i - 1\n",
        "    sequence[i+1] = key"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "mYDvHsnplNae",
        "outputId": "d8dfedc9-40c6-4f53-c24f-285f27f38b2a"
      },
      "source": [
        "def insertion_sort(numberSequence, compareFunction):\n",
        "   for j in range(1,len(numberSequence)):\n",
        "      merge(numberSequence, j-1, compareFunction)\n",
        "   return numberSequence\n",
        "\n",
        "insertion_sort([4,3,2,1], lambda a,b : a > b)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[4]\n",
            "[3, 4]\n",
            "[2, 3, 4]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4]"
            ]
          },
          "metadata": {},
          "execution_count": 220
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t04R8W_zlb5v",
        "outputId": "65164fc6-fdc9-499a-fd12-f7052858dcda"
      },
      "source": [
        "insertion_sort([1,2,3,4], lambda a,b : a < b)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[4, 3, 2, 1]"
            ]
          },
          "metadata": {},
          "execution_count": 132
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v5wS5kGorSY_",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "93798384-f502-4161-f374-54de84852636"
      },
      "source": [
        "def for_recursive(sequence, j=0):\n",
        "    if j <= len(sequence):\n",
        "      print(sequence[:j])\n",
        "      for_recursive(sequence,j+1)\n",
        "      \n",
        "for_recursive([1,2,3,4])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[]\n",
            "[1]\n",
            "[1, 2]\n",
            "[1, 2, 3]\n",
            "[1, 2, 3, 4]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lhn5RRXmynLG",
        "outputId": "aa35de40-0922-47ac-90dd-74eabe2aff93"
      },
      "source": [
        "def for_inverse_recursive(sequence, j=0):\n",
        "    if j <= len(sequence):\n",
        "      for_inverse_recursive(sequence,j+1)\n",
        "      print(sequence[:j])\n",
        "\n",
        "for_inverse_recursive([1,2,3,4])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4]\n",
            "[1, 2, 3]\n",
            "[1, 2]\n",
            "[1]\n",
            "[]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "S5M9_JTEyu4u",
        "outputId": "80c0a6d0-6efc-4237-a1fc-abddc0531255"
      },
      "source": [
        "def insertion_sort_recursive(sequence, j=1):\n",
        "     if j < len(sequence):\n",
        "         merge(sequence, j-1, lambda a,b: a > b)\n",
        "         insertion_sort_recursive(sequence,j+1)\n",
        "     return sequence\n",
        "\n",
        "insertion_sort_recursive([4,3,2,1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[4]\n",
            "[3, 4]\n",
            "[2, 3, 4]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4]"
            ]
          },
          "metadata": {},
          "execution_count": 223
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "87Hy2rB__wj8",
        "outputId": "df0cbd8e-9071-42b3-a106-b71d511c11f7"
      },
      "source": [
        "def insertion_sort_recursive_stack(sequence, n=-1):\n",
        "     n = len(sequence) if n == -1 else n  \n",
        "     if n > 1:\n",
        "         insertion_sort_recursive_stack(sequence, n-1)\n",
        "         merge(sequence, n-2, lambda a,b: a > b)\n",
        "     return sequence\n",
        "\n",
        "insertion_sort_recursive_stack([4,3,2,1])\n",
        "print()\n",
        "insertion_sort_recursive_stack([1,2,3,4])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[4]\n",
            "[3, 4]\n",
            "[2, 3, 4]\n",
            "\n",
            "[1]\n",
            "[1, 2]\n",
            "[1, 2, 3]\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[1, 2, 3, 4]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kCb6UDdXIn4A"
      },
      "source": [
        "import time\t\t\t\t\t\n",
        "import numpy as np\n",
        "from IPython.display import Math\n",
        "\n",
        "def timer(f, x):\n",
        "  times = []\n",
        "  for i in range(30):\n",
        "    tic = time.perf_counter()\n",
        "    f(x)\n",
        "    toc = time.perf_counter()\n",
        "    times.append(toc - tic)\n",
        "  print(\"Build finished in \")\n",
        "  output = f\"{np.mean(times):0.4f} \\pm {np.std(times):0.4f}  seconds\"\n",
        "  return Math(output)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AL4mEC4aETwU",
        "outputId": "6623fb9d-9500-4332-e2e5-9c11bf53ae2a"
      },
      "source": [
        "def merge(arr,L,R): \n",
        "      i = j = k = 0\n",
        "      while i < len(L) and j < len(R):\n",
        "          if L[i] < R[j]:\n",
        "            arr[k] = L[i]\n",
        "            i += 1\n",
        "          else:\n",
        "            arr[k] = R[j]\n",
        "            j += 1\n",
        "          k += 1\n",
        "      while i < len(L):\n",
        "          arr[k] = L[i]\n",
        "          i += 1\n",
        "          k += 1\n",
        "      while j < len(R):\n",
        "          arr[k] = R[j]\n",
        "          j += 1\n",
        "          k += 1\n",
        "\n",
        "def recursiveMergeSort(arr):\n",
        "    if len(arr) > 1:\n",
        "        mid = len(arr)//2\n",
        "        L = arr[:mid]\n",
        "        R = arr[mid:]\n",
        "        recursiveMergeSort(L)\n",
        "        recursiveMergeSort(R)\n",
        "        merge(arr,L,R)\n",
        "    return arr\n",
        "\n",
        "timer(recursiveMergeSort, np.random.rand(1,1000000)[0])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 1.1987 +- 0.0319 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "b3rnv4cNE8jl",
        "outputId": "df61deec-eb9f-489a-a52a-32cefaff833d"
      },
      "source": [
        "def mergeSort(a):\n",
        "    # start with least partition size of 2^0 = 1\n",
        "    width = 1   \n",
        "    n = len(a)                                         \n",
        "    # subarray size grows by powers of 2\n",
        "    # since growth of loop condition is exponential,\n",
        "    # time consumed is logarithmic (log2n)\n",
        "    while (width < n):\n",
        "        # always start from leftmost\n",
        "        l=0;\n",
        "        while (l < n):\n",
        "            r = min(l+(width*2-1), n-1)\n",
        "            m = (l+r)//2\n",
        "            # final merge should consider\n",
        "            # unmerged sublist if input arr\n",
        "            # size is not power of 2\n",
        "            if (width>n//2):       \n",
        "                m = r-(n%width)  \n",
        "            merge(a, l, m, r)\n",
        "            l += width*2\n",
        "        # Increasing sub array size by powers of 2\n",
        "        width *= 2\n",
        "    return a\n",
        "   \n",
        "# Merge Function\n",
        "def merge(a, l, m, r):\n",
        "    n1 = m - l + 1\n",
        "    n2 = r - m\n",
        "    L = [0] * n1\n",
        "    R = [0] * n2\n",
        "    for i in range(0, n1):\n",
        "        L[i] = a[l + i]\n",
        "    for i in range(0, n2):\n",
        "        R[i] = a[m + i + 1]\n",
        " \n",
        "    i, j, k = 0, 0, l\n",
        "    while i < n1 and j < n2:\n",
        "        if L[i] > R[j]:\n",
        "            a[k] = R[j]\n",
        "            j += 1\n",
        "        else:\n",
        "            a[k] = L[i]\n",
        "            i += 1\n",
        "        k += 1\n",
        " \n",
        "    while i < n1:\n",
        "        a[k] = L[i]\n",
        "        i += 1\n",
        "        k += 1\n",
        " \n",
        "    while j < n2:\n",
        "        a[k] = R[j]\n",
        "        j += 1\n",
        "        k += 1\n",
        " \n",
        "timer(mergeSort, np.random.rand(1,1000000)[0])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 1.0700 +- 0.0294 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t7Y_Gvq7n9sv",
        "outputId": "39d47825-f53f-4e79-bb9d-3a966dac6aa4"
      },
      "source": [
        "import math \n",
        "def recursive_binary_search(X,x, p, r): \n",
        "  mid = (p+r)//2\n",
        "  print(X[p:r], end=\",\")\n",
        "  print(X[mid])\n",
        "  if r < p:\n",
        "     return None \n",
        "  if X[mid] == x:\n",
        "    return mid\n",
        "  if X[mid] > x:\n",
        "     return recursive_binary_search(X,x, p, mid-1)\n",
        "  if X[mid] < x:\n",
        "     return recursive_binary_search(X,x, mid+1, r)\n",
        "\n",
        "def binary_search(X, x):\n",
        "  if X[-1] < x:\n",
        "    return None \n",
        "  return recursive_binary_search(X, x, 0, len(X))\n",
        "\n",
        "assert binary_search([1,2,3,4,5], 1) == 0, \"A[0] == 1\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 5) == 4, \"A[4] == 5\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 10) == None, \"A[] == None\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 3) == 2, \"A[] == None\" # Best case: T(n)=O(1)\n",
        "assert binary_search([1,2,3,4,5,6,7,8], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n",
        "print()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3, 4, 5],3\n",
            "[1],1\n",
            "\n",
            "[1, 2, 3, 4, 5],3\n",
            "[4, 5],5\n",
            "\n",
            "[1, 2, 3, 4, 5],3\n",
            "[1],1\n",
            "[1, 2, 3, 4],5\n",
            "\n",
            "\n",
            "[1, 2, 3, 4, 5],3\n",
            "[1, 2, 3, 4, 5, 6, 7, 8],5\n",
            "[1, 2, 3],2\n",
            "[],1\n",
            "[1, 2, 3, 4, 5, 6, 7],8\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "duiQehM92ac7",
        "outputId": "65a54d23-c3cb-4c6e-c5e1-2df48b192338"
      },
      "source": [
        "def binary_search(X, x):\n",
        "  if X[-1] < x:\n",
        "    return None\n",
        "  p = 0\n",
        "  r = len(X)\n",
        "  while p < r:\n",
        "    mid = (p+r)//2\n",
        "    if X[mid] == x:\n",
        "      return mid\n",
        "    if X[mid] < x:\n",
        "       p = mid + 1\n",
        "    if X[mid] > x:\n",
        "       r = mid - 1 \n",
        "  return None\n",
        "\n",
        "assert binary_search([1,2,3,4,5], 1) == 0, \"A[0] == 1\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 5) == 4, \"A[4] == 5\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 10) == None, \"A[] == None\"\n",
        "print()\n",
        "assert binary_search([1,2,3,4,5], 3) == 2, \"A[] == None\" # Best case: T(n)=O(1)\n",
        "assert binary_search([1,2,3,4,5,6,7,8], -1) == None, \"A[] == None\" # Worst case: T(n)=Theta(lg(n))\n",
        "print()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "\n",
            "\n",
            "\n",
            "\n",
            "\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ARIheWUxLt-8",
        "outputId": "6772735c-27df-4f3f-d734-68670692c747"
      },
      "source": [
        "import math\n",
        "ratio = 1.618033988749895\n",
        "sqrt5 = 2.2360679775\n",
        "\n",
        "def fibonacci_elementA(i):\n",
        "   return math.floor((math.pow(ratio, i)/sqrt5)+0.5)\n",
        "\n",
        "def fibonacciA(x):\n",
        "   return [fibonacci_elementA(i) for i in range(x)]\n",
        "\n",
        "timer(fibonacciA, 1475)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 0.0013 +- 0.0012 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ov83WPCS6Rnt",
        "outputId": "c8ddb047-a760-41c8-a338-5275b10a9566"
      },
      "source": [
        "# T(n)Theta(2^n)\n",
        "def fibonacci_elementB(n):\n",
        "  return n if n < 2 else fibonacciB(n-1) + fibonacciB(n-2)\n",
        "\n",
        "def fibonacciB(x):\n",
        "   return [fibonacci_elementB(i) for i in range(x)]\n",
        "\n",
        "timer(fibonacciB, 20)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 0.1112 +- 0.0353 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 60
        },
        "id": "ESDeuHDxGj1L",
        "outputId": "3a49a967-0b25-4fb2-acab-438c9a0d1f5a"
      },
      "source": [
        "from mpmath import *\n",
        "ratio = 1.618033988749895\n",
        "sqrt5 = 2.2360679775\n",
        "\n",
        "def fibonacci_elementC(i, dps=30):\n",
        "   mp.dps = dps\n",
        "   return floor((power(ratio,i)/sqrt5)+0.5)\n",
        "\n",
        "def fibonacciC(x):\n",
        "   return [fibonacci_elementC(i) for i in range(x)]\n",
        "\n",
        "timer(fibonacciC, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in \n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/latex": "$$0.4638 \\pm 0.0181  seconds$$",
            "text/plain": [
              "<IPython.core.display.Math object>"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nxdEejgXsLyp",
        "outputId": "2929482f-d715-4af0-af24-ac01c0ed28a9"
      },
      "source": [
        "fibonacci_elementC(10000000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "mpf('1.1298343786046051632158517439349e+2089876')"
            ]
          },
          "metadata": {},
          "execution_count": 23
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uG8PoRkO4Xk0",
        "outputId": "1e747b18-e32f-443e-b1d3-76f3ac494f4d"
      },
      "source": [
        "def fibonacciD(i):\n",
        "   x = [0,1]\n",
        "   for i in range(2,i):\n",
        "     x.append(x[i-2]+x[i-1])\n",
        "   return x\n",
        "\n",
        "timer(fibonacciD, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 0.0044 +- 0.0008 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HgOGjl1Y8avp",
        "outputId": "32b38a66-a7b8-4c58-8c87-568eff6877ce"
      },
      "source": [
        "timer(fibonacciD, 1475)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in 0.0005 +- 0.0001 seconds\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eAjvekpk1Oh6"
      },
      "source": [
        "from functools import lru_cache\n",
        "from mpmath import *\n",
        "ratio = 1.618033988749895\n",
        "sqrt5 = 2.2360679775\n",
        "\n",
        "# O(1)\n",
        "@lru_cache(maxsize=32)\n",
        "def fibonacci(i, dps=30):\n",
        "   mp.dps = dps\n",
        "   return floor((power(ratio,i)/sqrt5)+0.5)\n",
        "# 0 1 2 3 \n",
        "# 0 1 1 2 3 5\n",
        "assert fibonacci(1) == 1, \"F(1)=1\" \n",
        "assert fibonacci(2) == 1, \"F(2)=1\"\n",
        "assert fibonacci(3) == 2, \"F(3)=2\"\n",
        "assert fibonacci(50) == 12586269025, \"F(50)=12586269025\""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 59
        },
        "id": "A7E34HYA76Kg",
        "outputId": "ada97059-d47c-4e72-a63b-356676aba6f4"
      },
      "source": [
        "from functools import lru_cache\n",
        "from mpmath import *\n",
        "ratio = 1.618033988749895\n",
        "sqrt5 = 2.2360679775\n",
        "\n",
        "# O(1)\n",
        "@lru_cache(maxsize=32)\n",
        "def fibonacci_elementE(i, dps=30):\n",
        "   mp.dps = dps\n",
        "   return floor((power(ratio,i)/sqrt5)+0.5)\n",
        "   \n",
        "@lru_cache(maxsize=32)\n",
        "def fibonacciE(x):\n",
        "   return [fibonacci_elementE(i) for i in range(x)]\n",
        "\n",
        "timer(fibonacciE, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in \n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/latex": "$$0.0158 \\pm 0.0851  seconds$$",
            "text/plain": [
              "<IPython.core.display.Math object>"
            ]
          },
          "metadata": {},
          "execution_count": 14
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 59
        },
        "id": "MZQ0q89FFVep",
        "outputId": "a9fb34cd-a429-479f-88ce-6d08cff0dca5"
      },
      "source": [
        "from functools import lru_cache\n",
        "# T(n)= Theta(n)\n",
        "# S(n)= Theta(n)\n",
        "@lru_cache(maxsize=32)\n",
        "def fibonacciF(n):\n",
        "   x = [0,1]\n",
        "   for i in range(2,n):\n",
        "     x.append(x[i-2]+x[i-1])\n",
        "   return x\n",
        "\n",
        "timer(fibonacciF, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in \n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/latex": "$$0.0003 \\pm 0.0016  seconds$$",
            "text/plain": [
              "<IPython.core.display.Math object>"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 59
        },
        "id": "Ivf8gl3ATr6g",
        "outputId": "93509dd2-8029-4aa9-eebe-a23e68435c7a"
      },
      "source": [
        "from functools import lru_cache\n",
        "# T(n)= Theta(n)\n",
        "# S(n)= Theta(n)\n",
        "@lru_cache(maxsize=32)\n",
        "def fibonacciG(n):\n",
        "   x = [0,1]\n",
        "   for i in range(2,n):\n",
        "     x.append(x[i-2]+x[i-1])\n",
        "   return x[n-1]\n",
        "\n",
        "timer(fibonacciG, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in \n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/latex": "$$0.0004 \\pm 0.0020  seconds$$",
            "text/plain": [
              "<IPython.core.display.Math object>"
            ]
          },
          "metadata": {},
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 59
        },
        "id": "GmXQ-S4yT5Ft",
        "outputId": "88d98123-fcb1-497e-c18b-f17fdfd3a6fe"
      },
      "source": [
        "timer(fibonacciE, 10000)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Build finished in \n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/latex": "$$0.0000 \\pm 0.0000  seconds$$",
            "text/plain": [
              "<IPython.core.display.Math object>"
            ]
          },
          "metadata": {},
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IJX8R5kdUaVh",
        "outputId": "0ee49101-971d-4c93-ba02-3fc8efad95c6"
      },
      "source": [
        "fibonacci_elementE(10000, 2089)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "mpf('33644764876439916400815769589976078277491540121598258624968783032187393983272937480220981902421945505330411162204414862352539419893003230331211469105401819891464280931134789935010847082585417743397526537902805522516533878186308781596146011340513775346991228053661448198598751876535328889029120717497623929300246924400514970993768341462774994775768254846513002338877459453421149271615086279909221234553101677564170630050075245955519692502470738742379660856991066444206258808165652165135646622725572875663091902612272309931585516277475992594254193979017208096055803131937054956327964259681718821919839211299122369393992723073707267009019658577479713801227041638652656240330045949819420085971413007319627039581069899355886242076537925173531308834414999675251591358241183087502881505881044448277686014027101584484227633952346775935272858283007651161334683673909916296744232726220769302789400937707277496846580860627987841856477238200468779655463932740655857836750418244098472020885355509232878913261947040038737564308747597783383591268598241729421837886434406685268775496514359484451202776206326653541834967980593775845121553771544765853133992082721449920757980796959725331026662550083500929961963705413756197892937697200361789487613152732457599977602993970980512390443845336114103542939264948686799655520353918203970524639387471667289674599757320794139351207784612967222392475008953858559208139915414065830092743634769202224124898647431586475503650096231926568930139219606063541759445182284826992725569179564407494267781240823709114267545635717507109657792407983769307760802304728106286780341944909187280433076522059822645758199229178902231338865675005872340333771137208679551422499247187371089829530936820362966568301252767182762280385628471788927478288012469690835955413213338357388554300372467846384674196077057288000850192970641095110654740332234579129669896834554904235967154027963759254997513964371069845494650160128247992801902412125314906147247138185035198232086551203407976797819733468415774753321065220137591530492020962251008082510982814892002572343846610765309535613337532106561735.0')"
            ]
          },
          "metadata": {},
          "execution_count": 29
        }
      ]
    }
  ]
}