material/01-big-o-notation/03-intro-to-big-o.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[back](./02-example.ipynb)\n",
    "\n",
    "---\n",
    "## `Introducing Big O`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Big O` notation is a way to formalize fuzzy counting.\n",
    "\n",
    "It provides a way to formally convey the idea of how the runtime of an algorithm grows as the inputs grow."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Big O Definition`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We say that an algorithm is $O(f(n))$ if the number of simple operations a computer has to do is eventually less than a constant times $f(n)$, as $n$ increases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- $f(n)$ could be linear $(f(n) = n)$\n",
    "- $f(n)$ could be quadratic $(f(n) = n^2)$\n",
    "- $f(n)$ could be constant $(f(n) = 1)$\n",
    "- $f(n)$ could be something entirely different!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And when we usually speak of `Big O`, we usually speak of the upper bounds, for example\n",
    "\n",
    "```javascript\n",
    "function addUpTo(n) {\n",
    "  return n * (n + 1) / 2;\n",
    "}\n",
    "```\n",
    "\n",
    "This is always three operations, it's constant (in real life, there might be slight variation in the runtime) the overall trend is flat.\n",
    "\n",
    "And this _(Always 3 operations)_ is represented as $O(1)$, meaning as $n$ grows _(the input to the function grows)_, in this case it has no change, it is not reflected in the runtime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While we take a look at this one\n",
    "\n",
    "```javascript\n",
    "function addUpTo(n) {\n",
    "  let total = 0;\n",
    "  for (let i = 1; i <= n; i++) {\n",
    "    total += i;\n",
    "  }\n",
    "  return total;\n",
    "}\n",
    "```\n",
    "\n",
    "Here, the number of operations is (eventually) bounded by a multiple of $n$ (say, $10n$), so it doesn't matter if it's $10n$ or $20n$ or $50n$, it is just $O(n)$ because we simplify by the order of it's magnitude."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Few Examples`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `01`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "function countUpAndDown(n) {\n",
    "  console.log('Going up!');\n",
    "  for (let i = 0; i < n; i++) {\n",
    "    console.log(i);\n",
    "  }\n",
    "  console.log('At the top!\\nGoing down...');\n",
    "  for (let j = n - 1; j >= 0; j--) {\n",
    "    console.log(j);\n",
    "  }\n",
    "  console.log('Back down. Bye!');\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going up!\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "At the top!\n",
      "Going down...\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n",
      "Back down. Bye!\n"
     ]
    }
   ],
   "source": [
    "countUpAndDown(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we might consider that during the first loop, it's $O(n)$ and again during the second loop it is $O(n)$, so it should be $2n$, but instead it's still $O(n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `02`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "function printAllPairs(n) {\n",
    "  for (var i = 0; i < n; i++) {\n",
    "    for (var j = 0; j < n; j++) {\n",
    "      console.log(i, j);\n",
    "    }\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "0 1\n",
      "0 2\n",
      "1 0\n",
      "1 1\n",
      "1 2\n",
      "2 0\n",
      "2 1\n",
      "2 2\n"
     ]
    }
   ],
   "source": [
    "printAllPairs(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the first loop is $O(n)$ and the second loop is also $O(n)$, but the difference is that it is nested, so it not the same as $O(2n)$ which simplifies to $O(n)$.\n",
    "\n",
    "So, if an $O(n)$ operation is within another $O(n)$ operation, then it is $O(n * n)   \\Rightarrow   O(n^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Conclusion`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "[next](./04-simplifying-big-o-expression.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
}