M7_AST_02_Time_Complexity_C_Aish.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "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.8.5"
    },
    "colab": {
      "provenance": [],
      "include_colab_link": true
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/aisha-partha/AIMLOps-Assignments/blob/main/M7_AST_02_Time_Complexity_C_Aish.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EKnwjn7ApjTM"
      },
      "source": [
        "# Advanced Certification Programme in AI and MLOps\n",
        "## A programme by IISc and TalentSprint\n",
        "### Assignment 2: Time Complexity"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "owyUCpyPpjTO"
      },
      "source": [
        "## Learning Objectives"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EVaS2uqqpjTP"
      },
      "source": [
        "At the end of the experiment, you will be able to\n",
        "\n",
        "* understand the concept of computational complexity\n",
        "* understand time complexity, Big-O notation and their concern about developing algorithms\n",
        "* determine the time complexity of given algorithms"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UR5JQB6_pjTP"
      },
      "source": [
        "## Introduction"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uazcUKCqpjTP"
      },
      "source": [
        "**Computational complexity** is a field of computer science which analyzes algorithms based on the amount of resources required for running it. The amount of required resources varies based on the input size, so the complexity is generally expressed as a function of $n$, where $n$ is the size of the input.\n",
        "\n",
        "Also, when we are analyzing an algorithm we can consider:\n",
        "- time complexity and\n",
        "- space complexity\n",
        "\n",
        "The **space complexity** is basically the amount of memory space required to solve a problem in relation to the input size."
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Time Complexity\n",
        "\n",
        "It is the computational complexity that describes the amount of time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.\n",
        "\n",
        "When analyzing the time complexity of an algorithm we may find three cases:\n",
        "- best-case,\n",
        "- average-case, and\n",
        "- worst-case\n",
        "\n",
        "Suppose we have the following unsorted list $$[1, 5, 3, 9, 2, 4, 6, 7, 8]$$ and we need to find the index of a value in this list using linear search.\n",
        "\n",
        "- **best-case**: this is the complexity of solving the problem for the best input. In above example, the best case would be to search for the value 1. Since this is the first value of the list, it would be found in the first iteration.\n",
        "\n",
        "- **average-case**: this is the average complexity of solving the problem. This complexity is defined with respect to the distribution of the values in the input data. Based on above sample, we could say that the average-case would be when we are searching for some value in the “middle” of the list, for example, the value 2.\n",
        "\n",
        "- **worst-case**: this is the complexity of solving the problem for the worst input of size $n$. In our example, the worst-case would be to search for the value 8, which is the last element from the list.\n",
        "\n",
        "Usually, when describing the time complexity of an algorithm, the worst-case is considered."
      ],
      "metadata": {
        "id": "7SgH7GfJTGgt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Big-O Notation"
      ],
      "metadata": {
        "id": "a0iL-WXrUymU"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "In computer science, Big-O notation is used to classify algorithms according to how their running time or space requirements grow as the input size ($n$) grows. This notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.\n",
        "\n",
        "Some of the most common time complexities expressed using the Big-O notation are shown below.\n",
        "\n",
        "<br>\n",
        "\n",
        "| Big-O Notation |  Time Complexity Details |\n",
        "|:---------|:--------|\n",
        "| $O(1)$  | Constant Time Complexity $O(1)$ occurs when the program doesn’t contain any loops, recursive functions or call to any other functions. The run time, in this case, won’t change no matter what the input value is. |\n",
        "| $O(n)$ | Linear Time Complexity $O(n)$ occurs when the run time of the code increases at an order of magnitude proportional to n. Here n is the size of the input. |\n",
        "| $O(log\\ n)$ | Logarithmic Time Complexity $O(log\\ n)$ occurs when at each subsequent step in the algorithm, the time is decreased at a magnitude inversely proportional to N. This generally happens in Binary Search Algorithm. |\n",
        "| $O(n\\ log\\ n)$ | Linearithmic or Quasilinear Time Complexity. One example of an algorithm that runs with this time complexity is Quick Sort, Heap Sort, Merge Sort |\n",
        "| $O(n^2)$ | Quadratic Time Complexity |\n",
        "| $O(2^n)$ | Exponential Time Complexity |\n",
        "| $O(n!)$  | Factorial Time Complexity |\n",
        "<br>\n",
        "\n",
        "When using the Big-O notation, we describe the algorithm’s efficiency based on the increasing size of the input data ($n$). For example, if the input is a string, the $n$ will be the length of the string. If it is a list, the $n$ will be the length of the list and so on.\n",
        "\n",
        "Let’s go through these common time complexities and see how they differ from each other with examples.\n"
      ],
      "metadata": {
        "id": "camEN7_YU8YF"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Setup Steps:"
      ],
      "metadata": {
        "id": "rKQ0Fvl_jNqU"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "vMqB0QlhrA2i"
      },
      "outputs": [],
      "source": [
        "#@title Please enter your registration id to start: { run: \"auto\", display-mode: \"form\" }\n",
        "Id = \"2304896\" #@param {type:\"string\"}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "_LtlU7S7rA2k"
      },
      "outputs": [],
      "source": [
        "#@title Please enter your password (your registered phone number) to continue: { run: \"auto\", display-mode: \"form\" }\n",
        "password = \"9916583736\" #@param {type:\"string\"}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "cellView": "form",
        "id": "b3al3R8-rA2k",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "a17fa81c-3ca9-4a2d-ea54-2e23c73a7f1b"
      },
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.HTML object>"
            ],
            "text/html": [
              "<script src=\"https://dashboard.talentsprint.com/aiml/record_ip.html?traineeId=2304896&recordId=7834\"></script>"
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Setup completed successfully\n"
          ]
        }
      ],
      "source": [
        "#@title Run this cell to complete the setup for this Notebook\n",
        "from IPython import get_ipython\n",
        "\n",
        "ipython = get_ipython()\n",
        "\n",
        "notebook= \"M7_AST_02_Time_Complexity_C\" #name of the notebook\n",
        "\n",
        "def setup():\n",
        "#  ipython.magic(\"sx pip3 install torch\")\n",
        "\n",
        "    from IPython.display import HTML, display\n",
        "    display(HTML('<script src=\"https://dashboard.talentsprint.com/aiml/record_ip.html?traineeId={0}&recordId={1}\"></script>'.format(getId(),submission_id)))\n",
        "    print(\"Setup completed successfully\")\n",
        "    return\n",
        "\n",
        "def submit_notebook():\n",
        "    ipython.magic(\"notebook -e \"+ notebook + \".ipynb\")\n",
        "\n",
        "    import requests, json, base64, datetime\n",
        "\n",
        "    url = \"https://dashboard.talentsprint.com/xp/app/save_notebook_attempts\"\n",
        "    if not submission_id:\n",
        "      data = {\"id\" : getId(), \"notebook\" : notebook, \"mobile\" : getPassword()}\n",
        "      r = requests.post(url, data = data)\n",
        "      r = json.loads(r.text)\n",
        "\n",
        "      if r[\"status\"] == \"Success\":\n",
        "          return r[\"record_id\"]\n",
        "      elif \"err\" in r:\n",
        "        print(r[\"err\"])\n",
        "        return None\n",
        "      else:\n",
        "        print (\"Something is wrong, the notebook will not be submitted for grading\")\n",
        "        return None\n",
        "\n",
        "    elif getAnswer() and getComplexity() and getAdditional() and getConcepts() and getComments() and getMentorSupport():\n",
        "      f = open(notebook + \".ipynb\", \"rb\")\n",
        "      file_hash = base64.b64encode(f.read())\n",
        "\n",
        "      data = {\"complexity\" : Complexity, \"additional\" :Additional,\n",
        "              \"concepts\" : Concepts, \"record_id\" : submission_id,\n",
        "              \"answer\" : Answer, \"id\" : Id, \"file_hash\" : file_hash,\n",
        "              \"notebook\" : notebook,\n",
        "              \"feedback_experiments_input\" : Comments,\n",
        "              \"feedback_mentor_support\": Mentor_support}\n",
        "      r = requests.post(url, data = data)\n",
        "      r = json.loads(r.text)\n",
        "      if \"err\" in r:\n",
        "        print(r[\"err\"])\n",
        "        return None\n",
        "      else:\n",
        "        print(\"Your submission is successful.\")\n",
        "        print(\"Ref Id:\", submission_id)\n",
        "        print(\"Date of submission: \", r[\"date\"])\n",
        "        print(\"Time of submission: \", r[\"time\"])\n",
        "        print(\"View your submissions: https://aimlops-iisc.talentsprint.com/notebook_submissions\")\n",
        "        #print(\"For any queries/discrepancies, please connect with mentors through the chat icon in LMS dashboard.\")\n",
        "        return submission_id\n",
        "    else: submission_id\n",
        "\n",
        "\n",
        "def getAdditional():\n",
        "  try:\n",
        "    if not Additional:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Additional\n",
        "  except NameError:\n",
        "    print (\"Please answer Additional Question\")\n",
        "    return None\n",
        "\n",
        "def getComplexity():\n",
        "  try:\n",
        "    if not Complexity:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Complexity\n",
        "  except NameError:\n",
        "    print (\"Please answer Complexity Question\")\n",
        "    return None\n",
        "\n",
        "def getConcepts():\n",
        "  try:\n",
        "    if not Concepts:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Concepts\n",
        "  except NameError:\n",
        "    print (\"Please answer Concepts Question\")\n",
        "    return None\n",
        "\n",
        "\n",
        "# def getWalkthrough():\n",
        "#   try:\n",
        "#     if not Walkthrough:\n",
        "#       raise NameError\n",
        "#     else:\n",
        "#       return Walkthrough\n",
        "#   except NameError:\n",
        "#     print (\"Please answer Walkthrough Question\")\n",
        "#     return None\n",
        "\n",
        "def getComments():\n",
        "  try:\n",
        "    if not Comments:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Comments\n",
        "  except NameError:\n",
        "    print (\"Please answer Comments Question\")\n",
        "    return None\n",
        "\n",
        "\n",
        "def getMentorSupport():\n",
        "  try:\n",
        "    if not Mentor_support:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Mentor_support\n",
        "  except NameError:\n",
        "    print (\"Please answer Mentor support Question\")\n",
        "    return None\n",
        "\n",
        "def getAnswer():\n",
        "  try:\n",
        "    if not Answer:\n",
        "      raise NameError\n",
        "    else:\n",
        "      return Answer\n",
        "  except NameError:\n",
        "    print (\"Please answer Question\")\n",
        "    return None\n",
        "\n",
        "\n",
        "def getId():\n",
        "  try:\n",
        "    return Id if Id else None\n",
        "  except NameError:\n",
        "    return None\n",
        "\n",
        "def getPassword():\n",
        "  try:\n",
        "    return password if password else None\n",
        "  except NameError:\n",
        "    return None\n",
        "\n",
        "submission_id = None\n",
        "### Setup\n",
        "if getPassword() and getId():\n",
        "  submission_id = submit_notebook()\n",
        "  if submission_id:\n",
        "    setup()\n",
        "else:\n",
        "  print (\"Please complete Id and Password cells before running setup\")\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "47LuiF46pjTQ"
      },
      "source": [
        "### Import required packages"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ADzXQmpspjTQ"
      },
      "source": [
        "import time\n",
        "import numpy as np"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kxlkse6qpjTR"
      },
      "source": [
        "#### **Constant Time** --- $O(1)$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HOTcysxCpjTR"
      },
      "source": [
        "An algorithm is said to have a constant time when it is not dependent on the input data ($n$). No matter the size of the input data, the running time will always be the same. For example, consider two functions below:\n",
        "- is_bigger() - returns whether $a$ is greater than $b$\n",
        "- get_first() - returns the first element of a list"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "T4lSCu4gpjTS"
      },
      "source": [
        "# Create is_bigger() function\n",
        "\n",
        "def is_bigger(a, b):\n",
        "    if a > b:\n",
        "        return True\n",
        "    else:\n",
        "        return False"
      ],
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Initialize x, y\n",
        "x = 10\n",
        "y = 12\n",
        "\n",
        "# Perform is_bigger() function and check execution time\n",
        "begin = time.time()\n",
        "result = is_bigger(x, y)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "FWrQzGVbiN0f",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7a85e41b-1b09-46e9-9479-bd2731945493"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n",
            "Total runtime: 8.463859558105469e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Create get_first() function\n",
        "\n",
        "def get_first(data):\n",
        "    return data[0]\n",
        "\n",
        "# Input data\n",
        "data = [1, 2, 9, 8, 3, 4, 7, 6, 5]\n",
        "\n",
        "# Perform get_first() function and check execution time\n",
        "begin = time.time()\n",
        "result = get_first(data)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "0nc8bFAsZz0s",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "019ea7ff-51ff-4ce2-ab60-da7354da5c02"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1\n",
            "Total runtime: 6.818771362304688e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Here, independently of the input data size, they will always have the same running time since the first one only compares the two inputs and the second one only gets the first value from the list.\n",
        "\n",
        "An algorithm with constant time complexity is excellent since we don’t need to worry about the input size."
      ],
      "metadata": {
        "id": "Ge7IZa_BZ2jf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Linear Time** --- $O(n)$\n",
        "\n",
        "An algorithm is said to have a linear time complexity when the running time increases at most linearly with the size of the input data. This is the best possible time complexity when the algorithm must examine all values in the input data.\n",
        "\n",
        "For example, printing all the values in a list."
      ],
      "metadata": {
        "id": "_FkRp0AHBb5Z"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a list\n",
        "data = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
        "\n",
        "# Print all the values of list and check the execution time\n",
        "begin = time.time()\n",
        "\n",
        "for value in data:\n",
        "    print(value, end= \", \")\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "# Total time taken\n",
        "print(f\"\\n Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "QiVgLfx7AiLF",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1a3fa366-8a66-4db1-8609-221892df4a2a"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1, 2, 3, 4, 5, 6, 7, 8, 9, \n",
            " Total runtime: 0.00406956672668457 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now, increase the length of list and print all elements."
      ],
      "metadata": {
        "id": "pzp0RQV71NUd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a list\n",
        "data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]\n",
        "\n",
        "# Print all the values of list and check the execution time\n",
        "begin = time.time()\n",
        "\n",
        "for value in data:\n",
        "    print(value, end=\", \")\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "# Total time taken\n",
        "print(f\"\\n Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "EnnoBRHQJSRC",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dde4bfb8-74d5-4c41-ac3b-25b2adaa8a1a"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, \n",
            " Total runtime: 0.003294706344604492 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "From the above results, we can see that the execution time has increased almost linearly i.e. when we have doubled the elements within a list, the execution also gets doubled.\n",
        "\n",
        "Let’s take a look at the example of a linear search, where we need to find the position of an element in an unsorted list:"
      ],
      "metadata": {
        "id": "Aa7LQKjfBxmz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create linear_search() function\n",
        "def linear_search(data, value):\n",
        "    for index in range(len(data)):\n",
        "        if value == data[index]:\n",
        "            return index\n",
        "    raise ValueError('Value not found in the list')\n",
        "\n",
        "# Input data as list of 9 elements\n",
        "data = [1, 5, 3, 9, 2, 4, 6, 7, 8]\n",
        "\n",
        "# Perform linear_search() function and check execution time\n",
        "begin = time.time()\n",
        "result = linear_search(data, 8)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "O5Gno0qDBxEt",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dd1084a7-5a7a-45c9-b33c-dcd4f01e2407"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8\n",
            "Total runtime: 8.940696716308594e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Note that in this example, we need to look at all values in the list to find the value we are looking for.\n",
        "\n",
        "Now, let's increase the length of list and do a linear search."
      ],
      "metadata": {
        "id": "cJSCUkryMqUi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Input data as list of 18 elements\n",
        "data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 13, 12, 14, 16, 17, 18]\n",
        "\n",
        "# Perform linear_search() function and check execution time\n",
        "begin = time.time()\n",
        "result = linear_search(data, 18)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "xNTIZMyEJ6W0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7ac75b05-81c6-4627-ecd1-bd19e8eb7374"
      },
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "17\n",
            "Total runtime: 5.316734313964844e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "From the above results also we can see that the execution time has increased almost linearly."
      ],
      "metadata": {
        "id": "Yz1CCHt-CEUM"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bUUZvgj3boYU"
      },
      "source": [
        "#### **Logarithmic Time** --- $O(log\\ n)$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1FqcNn7gboYW"
      },
      "source": [
        "An algorithm is said to have a logarithmic time complexity when it reduces the size of the input data in each step (it does not need to look at all values of the input data).\n",
        "\n",
        "The algorithm runtime increases very slowly compared to an increase in input size."
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algorithms with logarithmic time complexity are commonly found in operations on binary trees or when using binary search. Let’s take a look at the example of a binary search, where we need to find the position of an element in a sorted list."
      ],
      "metadata": {
        "id": "ESrSnj8PAGVp"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Steps of the binary search:\n",
        "- Calculate the middle of the list.\n",
        "- If the searched value is lower than the value in the middle of the list, set a new right bounder.\n",
        "- If the searched value is higher than the value in the middle of the list, set a new left bounder.\n",
        "- If the search value is equal to the value in the middle of the list, return the middle (the index).\n",
        "- Repeat the steps above until the value is found or the left bounder is equal or higher the right bounder."
      ],
      "metadata": {
        "id": "zufsZW28ArWh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a function for performing binary search\n",
        "def binary_search(data, value):\n",
        "    n = len(data)\n",
        "    left = 0\n",
        "    right = n - 1\n",
        "    while left <= right:\n",
        "        middle = (left + right) // 2\n",
        "        if value < data[middle]:\n",
        "            right = middle - 1\n",
        "        elif value > data[middle]:\n",
        "            left = middle + 1\n",
        "        else:\n",
        "            return middle\n",
        "    raise ValueError('Value is not in the list')\n",
        "\n",
        "# Input data as a sorted list\n",
        "data = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
        "\n",
        "begin = time.time()\n",
        "result = binary_search(data, 8)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "jShGdyzKAEcZ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0921efd8-c1e0-4599-c93e-3c77730bab4a"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "7\n",
            "Total runtime: 9.131431579589844e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "It is important to understand that an algorithm that must access all elements of its input data cannot take logarithmic time, as the time taken for reading input of size $n$ is of the order of $n$."
      ],
      "metadata": {
        "id": "NbDRczeKBWgM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Quasilinear Time** --- $O(n\\ log\\ n)$\n",
        "\n",
        "An algorithm is said to have a quasilinear time complexity when each operation in the input data have a logarithm time complexity. It is commonly seen in sorting algorithms (e.g. mergesort, timsort, heapsort).\n",
        "\n",
        "For example: for each value in the data1 ($O(n)$) use the binary search ($O(log\\ n$)) to search the same value in data2."
      ],
      "metadata": {
        "id": "NRFnFp7NCKsD"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create data1 and data2\n",
        "data1 = [2, 3, 6, 8]\n",
        "data2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
        "result = []\n",
        "\n",
        "# Perform binary search for each element of data1 to search the same value in data2, and check the execution time\n",
        "begin = time.time()\n",
        "\n",
        "for value in data1:\n",
        "    result.append(binary_search(data2, value))\n",
        "\n",
        "end = time.time()\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "VwYYUSXBCBJ2",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0e39a785-9095-4c38-99d3-50f562c830c3"
      },
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 5, 7]\n",
            "Total runtime: 0.00012087821960449219 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Another, more complex example, can be found in the Mergesort algorithm. Mergesort is an efficient, general-purpose, comparison-based sorting algorithm which has quasilinear time complexity.\n",
        "\n",
        "It divides the input list of length $n$ in half successively until there are\n",
        "$n$ lists of size 1. Then, pairs of lists are merged together with the smaller first element among the pair of lists being\n",
        "added in each step. Through successive merging and through comparison of first elements, the sorted list is built.\n",
        "\n",
        "The following image exemplifies the steps taken by the Mergesort algorithm.\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/merge_sort.png\">\n",
        "</center>\n",
        "<br>\n",
        "\n",
        "Let’s see an example:"
      ],
      "metadata": {
        "id": "nwKv1nReCxH9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a function for performing merge sort\n",
        "\n",
        "def merge_sort(data):\n",
        "    if len(data) <= 1:\n",
        "        return\n",
        "\n",
        "    mid = len(data) // 2\n",
        "    left_data = data[:mid]\n",
        "    right_data = data[mid:]\n",
        "\n",
        "    merge_sort(left_data)\n",
        "    merge_sort(right_data)\n",
        "\n",
        "    left_index = 0\n",
        "    right_index = 0\n",
        "    data_index = 0\n",
        "\n",
        "    while left_index < len(left_data) and right_index < len(right_data):\n",
        "        if left_data[left_index] < right_data[right_index]:\n",
        "            data[data_index] = left_data[left_index]\n",
        "            left_index += 1\n",
        "        else:\n",
        "            data[data_index] = right_data[right_index]\n",
        "            right_index += 1\n",
        "        data_index += 1\n",
        "\n",
        "    if left_index < len(left_data):\n",
        "        del data[data_index:]\n",
        "        data += left_data[left_index:]\n",
        "    elif right_index < len(right_data):\n",
        "        del data[data_index:]\n",
        "        data += right_data[right_index:]\n"
      ],
      "metadata": {
        "id": "bV4l9NIBCqQ3"
      },
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Input data\n",
        "data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]\n",
        "\n",
        "# Perform merge_sort() function and check execution time\n",
        "begin = time.time()\n",
        "merge_sort(data)\n",
        "end = time.time()\n",
        "\n",
        "print(data)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "_W4BpYUsjysg",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7f4b72a1-72da-4e08-e499-350431ffa161"
      },
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
            "Total runtime: 0.00011444091796875 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Quadratic Time** --- $O(n^2)$\n",
        "An algorithm is said to have a quadratic time complexity when it needs to perform a linear time operation for each value in the input data.\n",
        "\n",
        "For example, printing the pairs of elements within a list."
      ],
      "metadata": {
        "id": "Fucm4hvCDnyy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Input data\n",
        "data = [1, 2, 3, 4]\n",
        "\n",
        "# Print the pairs of elements of a list\n",
        "begin = time.time()\n",
        "\n",
        "for x in data:\n",
        "    for y in data:\n",
        "        print(x, y)\n",
        "\n",
        "end = time.time()\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "ipyczWUYC737",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3280f5ad-057c-4ae7-83ab-5c30078af9e8"
      },
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 1\n",
            "1 2\n",
            "1 3\n",
            "1 4\n",
            "2 1\n",
            "2 2\n",
            "2 3\n",
            "2 4\n",
            "3 1\n",
            "3 2\n",
            "3 3\n",
            "3 4\n",
            "4 1\n",
            "4 2\n",
            "4 3\n",
            "4 4\n",
            "Total runtime: 0.0011963844299316406 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Bubble sort is a great example of quadratic time complexity since for each value it needs to compare to all other values in the list.\n",
        "\n",
        "The BubbleSort compares each successive pair of elements in an unordered list and inverts the elements if they are not in order.\n",
        "\n",
        "The following image exemplifies the steps taken by the Bubblesort algorithm.\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/bubble_sort.png\" width=600px>\n",
        "</center>\n",
        "<br>\n",
        "\n",
        "Let’s see an example:"
      ],
      "metadata": {
        "id": "R34dAlbJD-2j"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a function to perform Bubble sort\n",
        "def bubble_sort(data):\n",
        "    swapped = True\n",
        "    while swapped:\n",
        "        swapped = False\n",
        "        for i in range(len(data)-1):\n",
        "            if data[i] > data[i+1]:\n",
        "                data[i], data[i+1] = data[i+1], data[i]\n",
        "                swapped = True"
      ],
      "metadata": {
        "id": "05ky_HYeIHOJ"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Input data\n",
        "data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]\n",
        "\n",
        "# Perform bubble_sort() and check the execution time\n",
        "begin = time.time()\n",
        "bubble_sort(data)\n",
        "end = time.time()\n",
        "\n",
        "print(data)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "dpzE9XVID40Y",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "03d2353e-21ab-4bc4-f923-0127cb4afe12"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
            "Total runtime: 0.00010633468627929688 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Exponential Time** --- $O(2^n)$\n",
        "An algorithm is said to have an exponential time complexity when the growth doubles with each addition to the input data set. This kind of time complexity is usually seen in brute-force algorithms.\n",
        "\n",
        "An example of an exponential time algorithm is the recursive calculation of Fibonacci numbers:"
      ],
      "metadata": {
        "id": "B9G0OB1HEI0Q"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a function for getting the nth element of a Fibonacci series\n",
        "\n",
        "def fibonacci(n):\n",
        "    if n <= 1:\n",
        "        return n\n",
        "    return fibonacci(n-1) + fibonacci(n-2)"
      ],
      "metadata": {
        "id": "gig6w8FoEGAa"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "As we may have noticed, the time complexity of recursive functions is a little harder to define since it depends on how many times the function is called and the time complexity of a single function call.\n",
        "\n",
        "The following recursion tree was generated by the Fibonacci algorithm using n = 4:\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/fibonacci_4.png\">\n",
        "</center>\n",
        "<br>\n",
        "\n",
        "Note that it will call itself until it reaches the leaves. When reaching the leaves it returns the value itself."
      ],
      "metadata": {
        "id": "2uYR4JcWEvt4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Print 4th element of a Fibonacci series and check the execution time\n",
        "begin = time.time()\n",
        "result = fibonacci(4)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "Rj3DyxTWOTbz",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7ec4c5f1-df10-4c4d-d9d4-51ee84bed787"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "Total runtime: 9.298324584960938e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Now, look how the recursion tree grows just increasing the n to 6:\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/fibonacci_6.png\">\n",
        "</center>\n",
        "<br>\n"
      ],
      "metadata": {
        "id": "vx1haJYCORzB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Print 6th element of a fibonacci series and check the execution time\n",
        "begin = time.time()\n",
        "result = fibonacci(6)\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "ZLWW1WKUO4PX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "1708beea-1ad9-4eb6-ae78-ad9165af4d8f"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "8\n",
            "Total runtime: 9.417533874511719e-05 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### **Factorial Time** --- $O(n!)$\n",
        "\n",
        "An algorithm is said to have a factorial time complexity when it grows in a factorial way based on the size of the input data, for example:\n",
        "\n",
        "    2! = 2 x 1 = 2\n",
        "    3! = 3 x 2 x 1 = 6\n",
        "    4! = 4 x 3 x 2 x 1 = 24\n",
        "    5! = 5 x 4 x 3 x 2 x 1 = 120\n",
        "    6! = 6 x 5 x 4 x 3 x 2 x 1 = 720\n",
        "    7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040\n",
        "    8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320"
      ],
      "metadata": {
        "id": "d3XDzuFXGMJ-"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "A great example of an algorithm which has a factorial time complexity is the Heap’s algorithm, which is used for generating all possible permutations of $n$ objects.\n",
        "\n",
        "Heap found a systematic method for choosing at each step a pair of elements to switch, in order to produce every possible permutation of these elements exactly once."
      ],
      "metadata": {
        "id": "V4wEZ6NTGzyG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a function to perform Heap's permutation\n",
        "\n",
        "def heap_permutation(data, n):\n",
        "    if n == 1:\n",
        "        print(data)\n",
        "        return\n",
        "\n",
        "    for i in range(n):\n",
        "        heap_permutation(data, n - 1)\n",
        "        if n % 2 == 0:\n",
        "            data[i], data[n-1] = data[n-1], data[i]\n",
        "        else:\n",
        "            data[0], data[n-1] = data[n-1], data[0]\n",
        "\n",
        "# Input data\n",
        "data = [1, 2, 3]\n",
        "\n",
        "# Perform Heap's permutation and check the execution time\n",
        "begin = time.time()\n",
        "result = heap_permutation(data, len(data))\n",
        "end = time.time()\n",
        "\n",
        "print(result)\n",
        "\n",
        "# Total time taken\n",
        "print(f\"Total runtime: {end - begin} sec\")"
      ],
      "metadata": {
        "id": "CYboJUlMEoSO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "24ea350f-9cd9-4716-dabd-e94342999c38"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[1, 2, 3]\n",
            "[2, 1, 3]\n",
            "[3, 1, 2]\n",
            "[1, 3, 2]\n",
            "[2, 3, 1]\n",
            "[3, 2, 1]\n",
            "None\n",
            "Total runtime: 0.0030765533447265625 sec\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Note that it will grow in a factorial way, based on the size of the input data, so we can say the algorithm has factorial time complexity $O(n!)$."
      ],
      "metadata": {
        "id": "CV1tqh7kHIlf"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Analyze the time complexity of an algorithm"
      ],
      "metadata": {
        "id": "uLHY4rWgHdXb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "It is important to note that when analyzing the time complexity of an algorithm with several operations we need to describe the algorithm based on the largest complexity among all operations. For example, consider a function below:"
      ],
      "metadata": {
        "id": "YPvWgcCpHjWQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def my_function(data):\n",
        "    first_element = data[0]\n",
        "\n",
        "    for value in data:\n",
        "        print(value)\n",
        "\n",
        "    for x in data:\n",
        "        for y in data:\n",
        "            print(x, y)"
      ],
      "metadata": {
        "id": "WWOsfudHHEiA"
      },
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Even though the operations in `my_function` does not make sense we can see that it has multiple time complexities: $O(1) + O(n) + O(n^2)$.\n",
        "\n",
        "So, when increasing the size of the input data, the bottleneck of this algorithm will be the operation that takes $O(n^2)$. Based on this, we can describe the time complexity of this algorithm as $O(n^2)$."
      ],
      "metadata": {
        "id": "ZhiLN5HtHsRd"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Big-O Cheat Sheets\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/common_data_structures_options.png\">\n",
        "</center>\n",
        "<br>\n",
        "\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/array_sorting_algorithms.png\">\n",
        "</center>\n",
        "<br>\n",
        "\n",
        "\n",
        "<br>\n",
        "<figure>\n",
        "<center>\n",
        "<img src=\"https://cdn.iisc.talentsprint.com/CDS/Images/big_O_complexity_chart.jpeg\">\n",
        "</center>\n",
        "<br>"
      ],
      "metadata": {
        "id": "1a6p2MX4IAAb"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Find the time complexity of the following codes:"
      ],
      "metadata": {
        "id": "zp_j_BQPloNd"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Example 1**"
      ],
      "metadata": {
        "id": "EZ1dmqS70l2c"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Example 1\n",
        "\n",
        "# Initialize a and b with 0\n",
        "a = 0\n",
        "b = 0\n",
        "\n",
        "# For instance let N = 10, M = 15\n",
        "N = 10\n",
        "M = 15\n",
        "\n",
        "for i in range(N):\n",
        "    a = a + np.random.rand()\n",
        "\n",
        "for j in range(M):\n",
        "    b = b + np.random.rand()"
      ],
      "metadata": {
        "id": "ENyeVfWXmEGb"
      },
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "=> $O(N + M)$\n",
        "\n",
        "*Explanation*: The first loop is $O(N)$ and the second loop is $O(M)$. Since we don’t know which is bigger, we say this is $O(N + M)$. This can also be written as $O(max(N, M))$."
      ],
      "metadata": {
        "id": "Xbl7jmZwpF3g"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Example 2**"
      ],
      "metadata": {
        "id": "Wb1Oqd9w0qRv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Example 2\n",
        "\n",
        "# Initialize a with 0\n",
        "a = 0\n",
        "\n",
        "# For instance let N = 10\n",
        "N = 10\n",
        "\n",
        "for i in range(N):\n",
        "    for j in range(N, i, -1):\n",
        "        a = a + i + j"
      ],
      "metadata": {
        "id": "ekELCrYPqFJ6"
      },
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "=> $O(N^2)$\n",
        "\n",
        "*Explanation*:\n",
        "The above code runs total no of times\n",
        "\n",
        "$= N + (N – 1) + (N – 2) + … 1 + 0 $\n",
        "\n",
        "$= N * (N + 1) / 2 $\n",
        "\n",
        "$= 1/2 * N^2 + 1/2 * N $\n",
        "\n",
        "$O(N^2)$ times."
      ],
      "metadata": {
        "id": "dVGX2f9Ur_Va"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "**Example 3**"
      ],
      "metadata": {
        "id": "IzPSFv0_0rCm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Example 3\n",
        "\n",
        "# Initialize k with 0\n",
        "k = 0\n",
        "\n",
        "# For instance let n = 16\n",
        "n = 16\n",
        "\n",
        "for i in range(int(n/2), n+1):\n",
        "    j = 2\n",
        "    while (j <= n):\n",
        "        k = k + n/2\n",
        "        j = j * 2"
      ],
      "metadata": {
        "id": "ORvfteics2RE"
      },
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "=> $O(n\\ log\\ n)$\n",
        "\n",
        "*Explanation*: Here, $j$ keeps doubling till it is less than or equal to $n$. When we can double a number for several times till it is less than $n$, the time complexity would be $log(n)$.\n",
        "\n",
        "Let’s take the examples here.\n",
        "\n",
        "for $n = 16, j = 2, 4, 8, 16 $\n",
        "\n",
        "for $n = 32, j = 2, 4, 8, 16, 32 $\n",
        "\n",
        "So, $j$ would run for $O(log\\ n)$ steps.\n",
        "$i$ runs for $n/2$ steps.\n",
        "\n",
        "So, total steps $= O(n/ 2 * log\\ (n)) = O(n*log\\ n)$"
      ],
      "metadata": {
        "id": "Toc28KZwto5A"
      }
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VHfHdGCP_n6Y"
      },
      "source": [
        "### Please answer the questions below to complete the experiment:\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VgSwVENIPcM6"
      },
      "source": [
        "#@title When analyzing the time complexity of an algorithm with several operations we need to describe the algorithm based on: { run: \"auto\", form-width: \"500px\", display-mode: \"form\" }\n",
        "Answer = \"the largest complexity among all operations\" #@param [\"\", \"the largest complexity among all operations\", \"the smallest complexity among all operations\", \"the average complexity among all operations\"]"
      ],
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NMzKSbLIgFzQ"
      },
      "source": [
        "#@title How was the experiment? { run: \"auto\", form-width: \"500px\", display-mode: \"form\" }\n",
        "Complexity = \"Good and Challenging for me\" #@param [\"\",\"Too Simple, I am wasting time\", \"Good, But Not Challenging for me\", \"Good and Challenging for me\", \"Was Tough, but I did it\", \"Too Difficult for me\"]\n"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DjcH1VWSFI2l"
      },
      "source": [
        "#@title If it was too easy, what more would you have liked to be added? If it was very difficult, what would you have liked to have been removed? { run: \"auto\", display-mode: \"form\" }\n",
        "Additional = \"NA\" #@param {type:\"string\"}\n"
      ],
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4VBk_4VTAxCM"
      },
      "source": [
        "#@title Can you identify the concepts from the lecture which this experiment covered? { run: \"auto\", vertical-output: true, display-mode: \"form\" }\n",
        "Concepts = \"Yes\" #@param [\"\",\"Yes\", \"No\"]\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XH91cL1JWH7m"
      },
      "source": [
        "#@title  Text and image description/explanation and code comments within the experiment: { run: \"auto\", vertical-output: true, display-mode: \"form\" }\n",
        "Comments = \"Very Useful\" #@param [\"\",\"Very Useful\", \"Somewhat Useful\", \"Not Useful\", \"Didn't use\"]\n"
      ],
      "execution_count": 31,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "z8xLqj7VWIKW"
      },
      "source": [
        "#@title Mentor Support: { run: \"auto\", vertical-output: true, display-mode: \"form\" }\n",
        "Mentor_support = \"Very Useful\" #@param [\"\",\"Very Useful\", \"Somewhat Useful\", \"Not Useful\", \"Didn't use\"]\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FzAZHt1zw-Y-",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "6d311ecb-7962-453c-a666-473e01b65ce6"
      },
      "source": [
        "#@title Run this cell to submit your notebook for grading { vertical-output: true }\n",
        "try:\n",
        "  if submission_id:\n",
        "      return_id = submit_notebook()\n",
        "      if return_id : submission_id = return_id\n",
        "  else:\n",
        "      print(\"Please complete the setup first.\")\n",
        "except NameError:\n",
        "  print (\"Please complete the setup first.\")"
      ],
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Your submission is successful.\n",
            "Ref Id: 7834\n",
            "Date of submission:  26 Oct 2024\n",
            "Time of submission:  08:29:25\n",
            "View your submissions: https://aimlops-iisc.talentsprint.com/notebook_submissions\n"
          ]
        }
      ]
    }
  ]
}