{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Big O Examples\n",
    "\n",
    "In the first part of the Big-O example section we will go through various iterations of the various Big-O functions. Make sure to complete the reading assignment!\n",
    "\n",
    "Let's begin with some simple examples and explore what their Big-O is.\n",
    "\n",
    "## O(1) Constant"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def func_constant(values):\n",
    "    '''\n",
    "    Prints first item in a list of values.\n",
    "    '''\n",
    "    print values[0]\n",
    "    \n",
    "func_constant([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how this function is constant because regardless of the list size, the function will only ever take a constant step size, in this case 1, printing the first value from a list. so we can see here that an input list of 100 values will print just 1 item, a list of 10,000 values will print just 1 item, and a list of **n** values will print just 1 item!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## O(n) Linear"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "def func_lin(lst):\n",
    "    '''\n",
    "    Takes in list and prints out all values\n",
    "    '''\n",
    "    for val in lst:\n",
    "        print val\n",
    "        \n",
    "func_lin([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This function runs in O(n) (linear time). This means that the number of operations taking place scales linearly with n, so we can see here that an input list of 100 values will print 100 times, a list of 10,000 values will print 10,000 times, and a list of **n** values will print **n** times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## O(n^2) Quadratic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0\n",
      "0 1\n",
      "0 2\n",
      "0 3\n",
      "1 0\n",
      "1 1\n",
      "1 2\n",
      "1 3\n",
      "2 0\n",
      "2 1\n",
      "2 2\n",
      "2 3\n",
      "3 0\n",
      "3 1\n",
      "3 2\n",
      "3 3\n"
     ]
    }
   ],
   "source": [
    "def func_quad(lst):\n",
    "    '''\n",
    "    Prints pairs for every item in list.\n",
    "    '''\n",
    "    for item_1 in lst:\n",
    "        for item_2 in lst:\n",
    "            print item_1,item_2\n",
    "            \n",
    "lst = [0, 1, 2, 3]\n",
    "\n",
    "func_quad(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how we now have two loops, one nested inside another. This means that for a list of n items, we will have to perform n operations for *every item in the list!* This means in total, we will perform n times n assignments, or n^2. So a list of 10 items will have 10^2, or 100 operations. You can see how dangerous this can get for very large inputs! This is why Big-O is so important to be aware of!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "______\n",
    "## Calculating Scale of Big-O\n",
    "\n",
    "In this section we will discuss how insignificant terms drop out of Big-O notation.\n",
    "\n",
    "When it comes to Big O notation we only care about the most significant terms, remember as the input grows larger only the fastest growing terms will matter. If you've taken a calculus class before, this will reminf you of taking limits towards infinity. Let's see an example of how to drop constants:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_once(lst):\n",
    "    '''\n",
    "    Prints all items once\n",
    "    '''\n",
    "    for val in lst:\n",
    "        print val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print_once(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The print_once() function is O(n) since it will scale linearly with the input. What about the next example?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_3(lst):\n",
    "    '''\n",
    "    Prints all items three times\n",
    "    '''\n",
    "    for val in lst:\n",
    "        print val\n",
    "        \n",
    "    for val in lst:\n",
    "        print val\n",
    "        \n",
    "    for val in lst:\n",
    "        print val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "0\n",
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "print_3(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the first function will print O(n) items and the second will print O(3n) items. However for n going to inifinity the constant can be dropped, since it will not have a large effect, so both functions are O(n).\n",
    "\n",
    "Let's see a more complex example of this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def comp(lst):\n",
    "    '''\n",
    "    This function prints the first item O(1)\n",
    "    Then is prints the first 1/2 of the list O(n/2)\n",
    "    Then prints a string 10 times O(10)\n",
    "    '''\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": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n",
      "number\n"
     ]
    }
   ],
   "source": [
    "lst = [1,2,3,4,5,6,7,8,9,10]\n",
    "\n",
    "comp(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So let's break down the operations here. We can combine each operation to get the total Big-O of the function:\n",
    "\n",
    "$$O(1 + n/2 + 10)$$\n",
    "\n",
    "We can see that as n grows larger the 1 and 10 terms become insignificant and the 1/2 term multiplied against n will also not have much of an effect as n goes towards infinity. This means the function is simply O(n)!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Worst Case vs Best Case\n",
    "\n",
    "Many times we are only concerned with the worst possible case of an algorithm, but in an interview setting its important to keep in mind that worst case and best case scenarios may be completely different Big-O times. For example, consider the following function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def matcher(lst,match):\n",
    "    '''\n",
    "    Given a list lst, return a boolean indicating if match item is in the list\n",
    "    '''\n",
    "    for item in lst:\n",
    "        if item == match:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matcher(lst,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matcher(lst,11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that in the first scenario, the best case was actually O(1), since the match was found at the first element. In the case where there is no match, every element must be checked, this results in a worst case time of O(n). Later on we will also discuss average case time.\n",
    "\n",
    "Finally let's introduce the concept of space complexity.\n",
    "\n",
    "## Space Complexity\n",
    "\n",
    "Many times we are also concerned with how much memory/space an algorithm uses. The notation of space complexity is the same, but instead of checking the time of operations, we check the size of the allocation of memory.\n",
    "\n",
    "Let's see a few examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def printer(n=10):\n",
    "    '''\n",
    "    Prints \"hello world!\" n times\n",
    "    '''\n",
    "    for x in range(n):\n",
    "        print 'Hello World!'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n",
      "Hello World!\n"
     ]
    }
   ],
   "source": [
    "printer()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how we only assign the 'hello world!' variable once, not every time we print. So the algorithm has O(1) **space** complexity and an O(n) **time** complexity. \n",
    "\n",
    "Let's see an example of O(n) **space** complexity:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def create_list(n):\n",
    "    new_list = []\n",
    "    \n",
    "    for num in range(n):\n",
    "        new_list.append('new')\n",
    "    \n",
    "    return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['new', 'new', 'new', 'new', 'new']\n"
     ]
    }
   ],
   "source": [
    "print create_list(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note how the size of the new_list object scales with the input **n**, this shows that it is an O(n) algorithm with regards to **space** complexity.\n",
    "_____\n",
    "\n",
    "Thats it for this lecture, before continuing on, make sure to complete the homework assignment below:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework Assignment\n",
    "\n",
    "Your homework assignment after this lecture is to read the fantastic explanations of Big-O at these two sources:\n",
    "\n",
    "* [Big-O Notation Explained](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278)\n",
    "\n",
    "* [Big-O Examples Explained](http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}