material/01-big-o-notation/04-simplifying-big-o-expression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[back](./03-intro-to-big-o.ipynb)\n",
    "\n",
    "---\n",
    "## `Simplifying Big O expression`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Recap`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We already saw in [this section, `Counting Operations`](./02-example.ipynb) that how counting all the operations can be tricky and the exact count doesn't really matter and all that we really care about is the general trend. And in the referred section, we simplified from $5n + 2$ to just $n$, meaning that as $n$ grows, the runtime grows proportionately with $n$ and it doesn't matter if it is $2n$ or $5n$ etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Rule of simplify`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are some helpful rules of thumb for `Big O` expression that we can follow to help determine the `time complexity` of an algorithm.\n",
    "\n",
    "These rules of thumb are consequences of the definition of `Big O` notation that we only bother about the *broadest*, *fuzziest*, the *big-picture* view."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `01 - Constants Don't Matter`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If we have something like $O(2n)$, we simplify that to just $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If we have $O(500)$, meaning there are $500$ `operations` no matter what $n$ is, then the trend will be flat so, instead of saying $O(500)$ we just say it $O(1)$ _(constant runtime)_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If we have something like $O(13n^2)$, then again, we don't need that constant, it's just $O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `02 - Smaller Terms Don't Matter `"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Like $O(n + 10)$, we get rid of $10$, it's just $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- If it's $O(1000n + 50)$, in this case too it's just $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- And $O(n^2 + 5n + 8)$, if we look at the bigger-picture, a large number/input value, $5n + 8$ is meaning less, so it's just $O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `Big O Shorthands`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Analyzing complexity with `Big O` can get complicated.\n",
    "- There are several rules of thumb that can help, these rules won't **ALWAYS** work, but are helpful starting point."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.  Arithmetic operations are constants\n",
    "    - If you are adding something, dividing something and so on, it is going to be constant time, it doesn't really matter the size of the number.\n",
    "    - The computer will roughly take about the same number of time for $2 + 2$ as it does for $1000000 + 2$.\n",
    "1.  Variable assignment is constant\n",
    "    - So, the computer take roughly the same amount of time to make a variable $x = 100$ v/s $x = 2000000$.\n",
    "1.  Accessing elements in an array (by index) or object (by key) is constant\n",
    "1.  In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop\n",
    "    - If we have a loop, that is looping over $0$ to $n$, then the loop grows as $n$ grows.\n",
    "    - And then what ever happens inside the loop, is also consequential, like if we have a nested loop, then it could potentially be $n^2$ runtime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  `Some Examples`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `01`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "function logAtLeast5(n) {\n",
    "  for (let index = 0; index <= Math.max(5, n); index++) {\n",
    "    console.log(index);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the function logs the values up to $n$ times, but a minimum of at least till $5$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "logAtLeast5(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "logAtLeast5(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, what the `Big O` here, how would we categorize this?\n",
    "\n",
    "- So, we have a loop, that goes till $5$ or till $n$ whichever is the larger\n",
    "- We could worry about the $5$, but we only need to worry about it if the value of $n$ is small.\n",
    "- But, we care about what happens if $n$ grows larger, meaning when it keeps growing towards $\\infty$\n",
    "- So, we can simplify this and say it is $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `02`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "function logAtMost5(n) {\n",
    "  for (var index = 1; index <= Math.min(5, n); index++) {\n",
    "    console.log(index);\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "logAtMost5(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "logAtMost5(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, here, it's the opposite of the previous example, as $n$ grows, the loop only runs $5$ times. Meaning, the trend just stays flat after $n$ grows beyond $5$.\n",
    "\n",
    "So, rather than saying $O(5)$, it's just constant, which is $O(1)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> ### $O(1)$ v/s $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p align=\"center\">\n",
    "<img src=\"../../assets/Oof1vsOofN.png\" alt=\"O(1) vs O(n)\">\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $O(1)$ is pretty much a flat line, which is great to have a constant runtime, which is quite rare.\n",
    "- $O(n)$ is okay, the general trend is linear, which is better than other trends we see later like $O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Conclusion`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "[next](./05-space-complexity.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "18.3.0"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}