Algorithm Analysis and Big-O notation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm Analysis\n",
    "Algorithm is simply a procedure or formula for solving a problem. For comparing algorithms, the amount of space taken in memory or how much time is taken by each algorithm to run is considered."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sum1(n):\n",
    "    final_sum = 0\n",
    "    for x in range(n+1):\n",
    "        final_sum+=x\n",
    "    return final_sum\n",
    "\n",
    "sum1(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sum2(n):\n",
    "    return (n*(n+1))//2\n",
    "\n",
    "sum2(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.47 µs ± 18.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit sum1(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "140 ns ± 2.43 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit sum2(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The two functions take different times to execute. This shows **Time complexity**.  \n",
    "Big-O notation describes how quickly runtime will grow relative to the input as the input get arbitrarily large. It is a relative representation.\n",
    "* Remember, we want to compare how quickly runtime will grows, not compare exact runtimes, since those can vary depending on hardware.\n",
    "* Since we want to compare for a variety of input sizes, we are only concerned with runtime grow relative to the input. This is why we use n for notation.\n",
    "* As n gets arbitrarily large we only worry about terms that will grow the fastest as n gets large, to this point, Big-O analysis is also known as asymptotic analysis\n",
    "\n",
    "## Common Big-O functions\n",
    "**Big-O**|**Name**\n",
    ":-----:|:-----:\n",
    "1 |Constant\n",
    "log(n) |Logarithmic\n",
    "n |Linear\n",
    "nlog(n) |Log Linear\n",
    "n^2 |Quadratic\n",
    "n^3 |Cubic\n",
    "2^n |Exponential\n",
    "\n",
    "## Big-O examples\n",
    "Here is a real life example to understand the notations mentioned above. Take a phone book. It has businesses (the \"Yellow Pages\") which have unique names and people (the \"White Pages\") which may not have unique names. A phone number is assigned to at most one person or business. We will also assume that it takes constant time to flip to a specific page.\n",
    "* **O(1) (best case):** Given the page that a business's name is on and the business name, find the phone number.\n",
    "* **O(1) (average case):** Given the page that a person's name is on and their name, find the phone number.\n",
    "* **O(log n):** Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)\n",
    "* **O(n):** Find all people whose phone numbers contain the digit \"5\".\n",
    "* **O(n):** Given a phone number, find the person or business with that number.\n",
    "* **O(n log n):** There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.\n",
    "\n",
    "For the below examples, we're now at the printer's office. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.\n",
    "* **O(n log n):** We want to personalize the phone book, so we're going to find each person or business's name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage.\n",
    "* **O(n2):** A mistake occurred at the office, and every entry in each of the phone books has an extra \"0\" at the end of the phone number. Take some white-out and remove each zero.\n",
    "* **O(n · n!):** We're ready to load the phonebooks onto the shipping dock. Unfortunately, the robot that was supposed to load the books has gone haywire: it's putting the books onto the truck in a random order! Even worse, it loads all the books onto the truck, then checks to see if they're in the right order, and if not, it unloads them and starts over. (This is the dreaded bogo sort.)\n",
    "* **O(n^n):** You fix the robot so that it's loading things correctly. The next day, one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems. Every time the robot goes to load an original book, the factory printer makes a duplicate run of all the phonebooks! Fortunately, the robot's bug-detection systems are sophisticated enough that the robot doesn't try printing even more copies when it encounters a duplicate book for loading, but it still has to load every original and duplicate book that's been printed.\n",
    "\n",
    "The above illustration is taken from stackoverflow: https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly\n",
    "Additional reference for understanding O(nlogn): https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Irrespective of the list size, the time taken to print the first element will always be constant. Hence, \n",
    "the time complexity is O(1)\"\"\"\n",
    "\n",
    "lst = [1,2,3,4,5,6]\n",
    "\n",
    "def func_constant(values):\n",
    "    print(values[0])\n",
    "    \n",
    "func_constant(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "\"\"\"The time taken to print the entire list is proportional to the size of the list. Hence, \n",
    "the time complexity is O(n)\"\"\"\n",
    "\n",
    "def func_lin(lst):\n",
    "    for val in lst:\n",
    "        print(val)\n",
    "\n",
    "func_lin(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "1 2\n",
      "1 3\n",
      "2 1\n",
      "2 2\n",
      "2 3\n",
      "3 1\n",
      "3 2\n",
      "3 3\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Tthe time taken to print the combination of each element with each element of the list. n operations are performed\n",
    "for each element of the list. Hence, the time complexity is O(n^2)\"\"\"\n",
    "\n",
    "def func_quad(lst):\n",
    "    for item1 in lst:\n",
    "        for item2 in lst:\n",
    "            print(item1, item2)\n",
    "func_quad([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Calculating Big-O\n",
    "Different sections of a code might have different time complexities. The one with the most significant term is considered. This is because, as the input grows larger, only the fastes growing term will matter most."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"O(n)+O(n) = O(2n) = O(2*n)\n",
    "drop constants. Hence, time complexity is O(n)\"\"\"\n",
    "def func_lin(lst):\n",
    "    for val in lst:\n",
    "        print(val)\n",
    "    for val in lst:\n",
    "        print(val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"O(1) + O(n/2) + O(10) will equate to O(n)\"\"\"\n",
    "def comp(lst):\n",
    "    print(lst[0])\n",
    "    \n",
    "    midpoint = len(lst)/2\n",
    "    \n",
    "    for val in lst[:midpoint]:\n",
    "        print(val)\n",
    "        \n",
    "    for x in range(10):\n",
    "        print('number')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Worst and Best Case\n",
    "A given algorithm can have different time comlexities based on the input. Take the below code, for example. If the first element in the list is a match, the time complesxity will be O(1). If the last element matches, the complexity will be O(n). The former is the **best case** and the latter is called the **worst case**. Usually, the worst case is taken into account for time complexity measurements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matcher(lst,match):\n",
    "    for item in lst:\n",
    "        if item == match:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Space Complexity\n",
    "Notation for space complexity is the same as time comlexity. Here the amount of memory used for execution is taken into account."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Space for the string 'Hello World' is only required. Hence space complexity is O(1)\"\"\"\n",
    "\n",
    "def printer(n=10):\n",
    "    for x in range(n):\n",
    "        print('Hello World!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"Space for the lsit with n elements is required. Hence space complexity is O(n)\"\"\"\n",
    "\n",
    "def create_list(n):\n",
    "    new_list = []\n",
    "    for num in range(n):\n",
    "        new_list.append('new')\n",
    "    return new_list"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}