material/01-big-o-notation/06-logarithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[back](./05-space-complexity.ipynb)\n",
    "\n",
    "---\n",
    "## `Logarithms`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Up until now, we've come across some of the most common complexities, i.e., $O(1)$, $O(n)$, $O(n^2)$\n",
    "- Sometimes, `Big O` expressions involve more complex mathematical expressions.\n",
    "- One that appears more often than some might like is the `logarithm`! 😉"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `What's a log again?`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, logarithm is simply the inverse of exponentiation.\n",
    "\n",
    "Just like division and multiplication are a pair, logarithms and exponents are a pair."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This equation $log_2(8) = 3$ is read as $log$ base $2$ of $8$ is $3$, and what we're really asking or calculating here is to see $2$ to the power *what?* will give us the value $8$, which is $3$ in this case, meaning $2^3 = 8$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, the same equation written in syntactical way would be $log_2(value) = exponent \\longrightarrow 2^{exponent} = value$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly like we had $\\frac{1}{2} = 0.5$ we could switch that and say that $2^{0.5} = 1$, meaning exponentiation and logarithms are inverse to one another."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One more point to keep in mind is that, logarithm is not something that is always worked with base $2$, we could have $log_3$ of something, meaning, $3$ to power of *what?* gives $8$ may be."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The most common ones though are the binary logarithms, which is $log_2$, then there is also the base $10$, meaning $10$ to the power what gives us some answer etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, with algorithms, we tend to see the big-picture, so we'll omit the $2$ and going forward, we'll consider $log === log_2$, so as to not keep writing the subscript $2$ all the time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, the other reason being, it actually doesn't really matter at the end-of-the day, because if we're comparing the trend of a constant time - $O(1)$ and a quadratic time - $O(n^{2})$ and a $O(log \\text{ } n)$ time, it doesn't really matter if it's $log_2$ or $log_3$ or $log_{10}$\n",
    "\n",
    "It's going to be the general trend that we care about, but just to be clear, $log$ alone is not a mathematical operation on its own, we just can't take the $log$ of a number, we need to have a base. So ideally we need to say $log_2$ or $log_{10}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But, in further sections, around `Big O` notation and in general when we see $log$ it's just the shorthand for conveying $log_2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Rule of thumb`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `logarithm` of a number roughly measures the number of times we can divide that number by $2$ **before we get a value that's less than or equal to $1$**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Example`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `01`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\frac{8}{2} = 4$\n",
    "\n",
    "$\\frac{4}{2} = 2$\n",
    "\n",
    "$\\frac{2}{2} = 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we have $8$ and we divide it by $2$, we get $4$ and is still greater than $1$, so we divide it by $2$ again, we get $2$ and we divide it by $2$ again and it's $1$ now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meaning, we divided it $3$ times, so $log(8) = 3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `02`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now considering 25, and this doesn't divide evenly with $2$.\n",
    "\n",
    "$\\frac{25}{2} \\text{ is } 12.5$\n",
    "\n",
    "$\\frac{12.5}{2} \\text{ is } 6.25$\n",
    "\n",
    "$\\frac{6.25}{2} \\text{ is } 3.125$\n",
    "\n",
    "$\\frac{3.125}{2} \\text{ is } 1.5625$\n",
    "\n",
    "and finally,\n",
    "\n",
    "$\\frac{1.5625}{2} = 0.78125$\n",
    "\n",
    "So, this tell us that somewhere between $4$ and $5$, and the answer is $log(25) \\approx 4.64$\n",
    "\n",
    "And the actual calculation is not that important here, rather what it would look on a trend chart."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Logarithm Complexity`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, `logarithm` time complexity is great!, if we have an algorithm with $log  n$ time complexity as seen below compared with previously seen `Big O` complexities.\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"../../assets/log_n_with_others.png\" alt=\"Log N with Other Complexities\">\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Who cares about logarithmic complexities?`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Certain searching algorithms have `logarithmic` time complexities, which we will see in later sections.\n",
    "- Also, efficient sorting algorithms have `logarithmic` complexities, we'll see these as well.\n",
    "- And finally, `recursions` sometimes involves `logarithmic` **space** complexities and not *time*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `Conclusion`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "[next](../02-analyzing-performance/00-index.ipynb)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "name": "javascript"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}