{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# Computing Maximum\n",
        "\n",
        "Consider the following three algorithms that compute the maximum of a given list :\n",
        "\n",
        "\n",
        "*   *max_1* - iteratively compares max with current element, and replaces if current element is larger than max\n",
        "\n",
        "*  *max_2* : computes the maximum of the left half and the right half separately - then returns the higher of these two\n",
        "\n",
        "*  *max_3* : computes the maximum of the first $(n-1)$ elements and the last $(n-1)$ elements separately - then returns the higher of these two\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "tRybFZcadKWF"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "F-BXCyCxdJnS",
        "outputId": "a906fec4-7a9a-4cc9-877f-6552e3e412b1"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[-32, 13, -86, 19, 10, 96, -67, -20, -66, -49, -98, -62, -70, -74, -23, 3, 63, 59, 92, 87, 4, -68, 73, -38, -25, -8, -13, 26, 7, -88]\n",
            "96\n"
          ]
        }
      ],
      "source": [
        "import random\n",
        "\n",
        "def max_1(l):\n",
        "\n",
        "  #setting max to lowest integer in python to avoid wrong answers\n",
        "  max = float(\"-inf\")\n",
        "\n",
        "  #print(max)\n",
        "\n",
        "  k = len(l)\n",
        "  for i in range(k):\n",
        "\n",
        "    if (l[i] > max):\n",
        "      max = l[i]\n",
        "\n",
        "  return max\n",
        "\n",
        "li = random.sample(range(-100,100),30)\n",
        "print(li)\n",
        "print(max_1(li))\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import random\n",
        "\n",
        "def max_2(l):\n",
        "  max = 0\n",
        "  #max = 0 is redundant\n",
        "  k = len(l)\n",
        "  if (k == 1):\n",
        "    return l[0]\n",
        "\n",
        "  first_half = max_2(l[0:k//2])\n",
        "\n",
        "  second_half = max_2(l[k//2:])\n",
        "\n",
        "  if (first_half > second_half):\n",
        "    return first_half\n",
        "  else:\n",
        "    return second_half\n",
        "\n",
        "li = [84, -75, -15, 86, 32, 50, -56, -49, 9, -77]\n",
        "li = random.sample(range(-100,100),30)\n",
        "print(li)\n",
        "#li = [-84, -75, -15, -86, -32, -50, -56, -49, -9, -77]\n",
        "print(max_2(li))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "N86TRKJYfKfA",
        "outputId": "6cf8c9fb-0dfb-4d91-dac8-1bd1ed156bed"
      },
      "execution_count": 51,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[85, -1, -24, 51, 99, -44, 18, 68, 34, 52, 63, 46, 40, -34, -17, -26, 95, 19, -6, -36, -15, 5, 92, 39, -65, -3, 56, 61, 71, 32]\n",
            "99\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "import random\n",
        "\n",
        "def max_3(l):\n",
        "  max = 0\n",
        "  #max= 0 is redundant\n",
        "\n",
        "  #next is base case\n",
        "  if(len(l) == 1):\n",
        "    return l[0]\n",
        "\n",
        "  #first, left = maximum of first (n-1) elements\n",
        "  left = max_3(l[:-1])\n",
        "\n",
        "  #next, right = maximum of last (n-1) elements\n",
        "  right = max_3(l[1:])\n",
        "\n",
        "  #comparing left vs right\n",
        "  if (left > right):\n",
        "    return left\n",
        "  else:\n",
        "    return right\n",
        "\n",
        "#li = random.sample(range(0,100),10)\n",
        "[84, -75, -15, 86, 32, 50, -56, -49, 9, -77]\n",
        "li = random.sample(range(-100,100),30)\n",
        "print(li)\n",
        "print(max_3(li))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 347
        },
        "id": "zpZnBBsOfsyD",
        "outputId": "8cefa35a-6bd4-4758-c8b8-ddc4b16eab03"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[-51, 56, -20, -3, 74, 18, -86, -39, 77, -34, -21, 78, -4, -84, -72, 2, 92, -63, -81, -69, -78, -66, 3, 15, 44, -94, 69, 73, -93, 4]\n"
          ]
        },
        {
          "output_type": "error",
          "ename": "KeyboardInterrupt",
          "evalue": "",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36m<cell line: 0>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     25\u001b[0m \u001b[0mli\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mrandom\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msample\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m100\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m100\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m30\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     26\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mli\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 27\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mli\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 15\u001b[0;31m   \u001b[0mright\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m   \u001b[0;31m#comparing left vs right\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m     10\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m   \u001b[0;31m#first, left = maximum of first (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m   \u001b[0mleft\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m   \u001b[0;31m#next, right = maximum of last (n-1) elements\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;32m/tmp/ipython-input-2008121862.py\u001b[0m in \u001b[0;36mmax_3\u001b[0;34m(l)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mrandom\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;32mdef\u001b[0m \u001b[0mmax_3\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ml\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m   \u001b[0mmax\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m   \u001b[0;31m#max= 0 is redundant\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Correctness**\n",
        "\n",
        "\n",
        "\n",
        "> Do all three algorithms always return the correct maximum of any given list of integers?\n",
        "\n"
      ],
      "metadata": {
        "id": "ZRbDL-DOjNiI"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Fixes**\n",
        "\n",
        "\n",
        "\n",
        "*   Fix for *max_1* :\n",
        "*   Fix for *max_2* :\n",
        "*   Fix for *max_3* :\n",
        "\n"
      ],
      "metadata": {
        "id": "SaH9iYqEjczB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Runtimes\n",
        "\n",
        "1.   Do all three algorithms execute instantly for inputs of size 10?\n",
        "\n",
        "2.   Do all three algorithms execute instantly for inputs of size 20?\n",
        "\n",
        "3.   Do all three algorithms execute instantly for inputs of size 30?\n",
        "\n",
        "\n",
        "\n",
        "> Why?\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "ZzypE6E7joKE"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Asymptotic run times\n",
        "\n",
        "\n",
        "\n",
        "1.   What is the asymptotic run time for *max_1*?\n",
        "\n",
        "\n",
        "\n",
        "*   Number of iterations of the for loop : $n$\n",
        "*   Time spend in each iteration : $O(1)$\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*   List item\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "3.   What is the asymptotic run time for *max_3*? How did you conclude this?\n",
        "\n",
        "\n",
        "Be mindful - number of comparisons vs runtime difference"
      ],
      "metadata": {
        "id": "mcH2i67qj5hi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Asymptotic run time for *max_2*\n",
        "\n",
        "\n",
        "\n",
        "*   Let $a(n)$ denote the total time taken by *max_2* on a list of size $n$. Then : $$a(n) = a(n/2) + a(n/2) + O(1)$$\n",
        "\n",
        "where -\n",
        "\n",
        "* the first $a(n/2)$ denotes the time taken by *max_2* on the first_half of the list - that is, by *max_2(l[0:n/2])*\n",
        "\n",
        "* the second $a(n/2)$ denotes the time taken by *max_2* on the second_half of the list - that is, by *max_2(l[n/2:])*\n",
        "\n",
        "* $O(1)$ is the total time taken by the first recursive call.\n",
        "\n",
        "*   Base case : $a(1) = O(1)$\n",
        "\n",
        "Recursion details :\n",
        "\n",
        "*   Number of levels to reach base case : $O(\\log_{2}{n})$ since $n$ is halved at each recursive call\n",
        "*   Number of function calls : $O(n)$ as we saw in class\n",
        "*   Time taken to return each recursive call : $O(1)$\n",
        "\n",
        "Total running time = $O(n) \\times O(1)$ = $O(n)$\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "QOrVMyfsxEQy"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Asymptotic run time for *max_3*\n",
        "\n",
        "\n",
        "\n",
        "*   Let $b(n)$ denote the total time taken by *max_3* on a list of size $n$. Then : $$b(n) = b(n-1) + b(n-1) + O(1)$$\n",
        "\n",
        "where -\n",
        "\n",
        "* the first $b(n-1)$ denotes the time taken by *max_3* on the first $(n-1) $ elements of the list - that is, by *max_3(l[0:(n-1)])*\n",
        "\n",
        "* the second $b(n-1)$ denotes the time taken by *max_3* on the last $(n-1)$ elements of the list - that is, by *max_3(l[1:n])*\n",
        "\n",
        "* $O(1)$ is the total time taken by the first recursive call.\n",
        "\n",
        "*   Base case : $b(1) = O(1)$\n",
        "\n",
        "Recursion details :\n",
        "\n",
        "*   Number of levels to reach base case : $O(n)$ since $n$ is reduced by 1 after each recursive call\n",
        "*   Number of function calls : $O(2^{n})$\n",
        "*   Time taken to return each recursive call : $O(1)$\n",
        "\n",
        "Total running time = $O(2^{n}) \\times O(1)$ = $O(2^{n})$\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "> *max_3* is inefficient as its run time is $O(2^{n})$ - this is why it did not compute the maximum for the 30 sized list!\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "nRApyHH_yZC4"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Recurrence trees (example)\n",
        "\n",
        "\n",
        "\n",
        "*   For a list of size 4, draw the recurrence tree for *max_2* that shows the recursive calls that *max_2* makes.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*   For a list of size 4, draw the recurrence tree for *max_3* that shows the recursive calls that *max_3* makes.\n",
        "\n"
      ],
      "metadata": {
        "id": "rxDEY7Cvka3n"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Understanding recurrences through recurrence trees\n",
        "\n",
        "Recurrence trees help you identify:\n",
        "\n",
        "\n",
        "\n",
        "*   Recursive calls made\n",
        "*   How many levels before we reach the base case\n",
        "*   Work done at each level\n",
        "\n"
      ],
      "metadata": {
        "id": "wsNUQ6PMpcVe"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Using the example recurrence trees for 4 sized lists as a reference, generalize these to $n$ sized lists.\n",
        "\n",
        "\n",
        "\n",
        "*   What is the first recursive call?\n",
        "\n",
        "*   What about recursive calls at the second level?\n",
        "\n",
        "*   How much work is done before/after the second level calls return to the first level?\n",
        "\n",
        "*   What about the third level? Do you see a pattern?\n",
        "\n",
        "*   How many levels does this tree have? How many nodes?\n",
        "\n"
      ],
      "metadata": {
        "id": "gbCA_0Yip0_D"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Recurrences for problems we have seen/discussed\n",
        "\n",
        "\n",
        "\n",
        "1.   Write a recurrence relation to characterize run time of the reversing a string probem from lab 2. Solve it after answering the questions on the previous slide.\n",
        "\n",
        "2.   Write recurrence relations for *mult_rec* and *mult_fast* from lecture 2. Can you solve them and analyze their asymptotic run times?\n",
        "\n"
      ],
      "metadata": {
        "id": "8O-AylwNqmNS"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "9suETPIEo8tA"
      },
      "execution_count": 26,
      "outputs": []
    }
  ]
}