Algorithim analysis and Big O notation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Big O notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's say we have two functions, a and b;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def a(n):\n",
    "    final = 0\n",
    "    for i in range(n+1):\n",
    "        final += i\n",
    "    return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def b(n):\n",
    "    return (n*(n+1))/2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These two functions both do the exact same thing; add up all the positive integers up to the input number. One is much shorter than the other, but there is no way we know yet that tells us which one is objectively better, which means more efficient. That's where Big O notation comes in - Big O notation tells us how much the runtime is going to grow relative to the input as the input grows. There are many ways to write the notation, each meaning different things. Here they are; \n",
    "\n",
    "\n",
    "Big-O___________Name\n",
    "\n",
    "1_______________Constant\n",
    "\n",
    "n_______________Linear\n",
    "\n",
    "n^2_____________Quadratic\n",
    "\n",
    "log(n)__________Logarithmic\n",
    "\n",
    "nlog(n)_________Log Linear\n",
    "\n",
    "n^3_____________Cubic\n",
    "\n",
    "2^n_____________Exponential\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, lets see how to find what notation is for what function, starting with a Constant Function. This function will have the same runtime, regardless of the input;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello World\n"
     ]
    }
   ],
   "source": [
    "def constant(n):\n",
    "    print('Hello World')\n",
    "constant('abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, lets see a Linear function which goes through each object in a list and prints it. It is linear, as the runtime is directly proportional to the input size, because the for loop runs as many times as there is an object in a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def linear(l):\n",
    "    for i in l:\n",
    "        print(i)\n",
    "linear([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, lets look at a quadratic function that has two variables which iterate through each item in the list. THis is quadratic because, for every item added, the loop will have its runtime go up significantly;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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": [
    "def quadratic(lst):\n",
    "    for n1 in lst:\n",
    "        for n2 in lst:\n",
    "            print(n1,n2)\n",
    "quadratic([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the number of outputs (9) is equal to the length of the list (3) squared. To prove this point, i will run the function but with a fourth value, and you will see that it will give 16 outputs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "1 2\n",
      "1 3\n",
      "1 4\n",
      "2 1\n",
      "2 2\n",
      "2 3\n",
      "2 4\n",
      "3 1\n",
      "3 2\n",
      "3 3\n",
      "3 4\n",
      "4 1\n",
      "4 2\n",
      "4 3\n",
      "4 4\n"
     ]
    }
   ],
   "source": [
    "quadratic([1,2,3,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voila!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "YOu get the idea. NOw, lets talk about another way of judging functions in python; Space complexity. This is basically judging how much is output based on the input size, so the two functions below, while one is much faster, both take up the same space and are equal based on space complexity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def slow(n):\n",
    "    nlist = []\n",
    "    for i in range(n):\n",
    "        nlist.append('new item')\n",
    "    return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}