material/01-big-o-notation/02-example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[back](./01-big-o-notation.ipynb)\n",
    "\n",
    "---\n",
    "## `Example`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Suppose we want to write a function that calculates the sum of all numbers from $1$ up to (and including) some number $n$.\n",
    "so, if we pass $3$ as input, it should return $(1 + 2 + 3) = 6$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Easiest solution would be"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "function addUpTo(n) {\n",
    "  let total = 0;\n",
    "  for (let i = 1; i <= n; i++) {\n",
    "    total += i;\n",
    "  }\n",
    "  return total;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "console.log(addUpTo(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- And there is another solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "function addUpTo(n) {\n",
    "  return n * (n + 1) / 2;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "console.log(addUpTo(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the second solution is much smaller, it's a mathematical equation, but it might necessarily better performing than the previous solution with a **for** loop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Which one is better?`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What does better mean?\n",
    "  - Faster?\n",
    "  - Less memory-intensive?\n",
    "  - More readable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, we'll evaluate first on how long the code takes to execute.\n",
    "And to do that, we can utilize the inbuilt timing functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time elapsed: 0.63322066700086 seconds.\n"
     ]
    }
   ],
   "source": [
    "function addUpTo(n) {\n",
    "  let total = 0;\n",
    "  for (let i = 1; i <= n; i++) {\n",
    "    total += 1;\n",
    "  }\n",
    "  return total;\n",
    "}\n",
    "\n",
    "let t1 = performance.now();\n",
    "addUpTo(1000000000);\n",
    "let t2 = performance.now();\n",
    "\n",
    "console.log(`Time elapsed: ${(t2 - t1) / 1000} seconds.`);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Time elapsed: 0.00001575000025331974 seconds.\n"
     ]
    }
   ],
   "source": [
    "function addUpTo(n) {\n",
    "    return (n * (n + 1)) / 2;\n",
    "}\n",
    "\n",
    "let t3 = performance.now();\n",
    "addUpTo(1000000000);\n",
    "let t4 = performance.now();\n",
    "\n",
    "console.log(`Time elapsed: ${(t4 - t3) / 1000} seconds.`);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that the second solution is way more efficient in terms of run time. But this process is not the most reliable of manually timing things before and after and comparing it with other function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `The problem with time`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Different machines will record different times, so it's not reliable.\n",
    "- It might not make the first result better than the second one, but the margin might change, the measurement can change.\n",
    "- The *same* machine can record different times!, meaning, this method might not be precise.\n",
    "- For fast algorithms, speed measurements might not be precise enough. And if our timing function is not able to get the difference then it doesn't help us."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `If not time, then what?`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Rather than counting seconds, which are so variable, we can count the *number* of simple operations the computer has to perform!\n",
    "- So, for example, if the first algorithm has 5 operations and the other has 7, then irrespective of the system it's running on, it will be the same number of operations \n",
    "- So, rather than the time, we can rely on the number of simple operations that the system has to perform."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Counting Operations`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, for example, in the below function, the shorter function\n",
    "\n",
    "  ```javascript\n",
    "  function addUpTo(n) {\n",
    "    return n * (n + 1) / 2;\n",
    "  }\n",
    "  ```\n",
    "- We first have $1 multiplication$, then $1 addition$, and at the end, $1 division$\n",
    "- So, total there are 3 operations, it doesn't matter what $n$ is, it could be one or a billion.\n",
    "- Hence, there are only 3 operations, regardless of the size of $n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparing it with our first solution.\n",
    "\n",
    "```javascript\n",
    "function addUpTo(n) {\n",
    "  let total = 0;\n",
    "  for (let i = 1; i <= n; i++) {\n",
    "    total += 1;\n",
    "  }\n",
    "  return total;\n",
    "}\n",
    "```\n",
    "\n",
    "- We see $total += 1$, so that is $1$ `operation`.\n",
    "- But, this is in a loop, meaning, if the value of $n$ is say $5$, then there will be $5$ `operations`.\n",
    "- So, it not $1$ `operation` anymore, instead it is $n$ `operations`.\n",
    "- And, it's not just that, the $=$ sign, the assignment operation is also an operation.\n",
    "- We also have $i++$ which is $1$ `addition` and $1$ `assignment operation`. And this too grows based on the value on $n$.\n",
    "- We have $total = 0$ which happens once, and it's $1$ `operation`.\n",
    "- Then there is $i = 1$ which is $1$ `assignment operation`.\n",
    "- And lastly, we have $i  \\leq  n$ `comparison operation`, which happens $n$ times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Clearly, the first solution doesn't have a static number of operations that we can count, so how do we generalize it?\n",
    "- So, depending on how we count, it can be as low as $2n$, or it can be as high as $5n + 2$.\n",
    "- But regardless of the exact number, the number of operations grows roughly *proportionally* with $n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Performance tracker app](https://rithmschool.github.io/function-timer-demo/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "[next](./03-intro-to-big-o.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
}