02. Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Analysis\n",
    "## 2.1. Objectives\n",
    "* To understand why algorithm analysis is important.\n",
    "* To be able to use “Big-O” to describe execution time.\n",
    "* To understand the “Big-O” execution time of common operations on Python lists and dictionaries.\n",
    "* To understand how the implementation of Python data impacts algorithm analysis.\n",
    "* To understand how to benchmark simple Python programs.\n",
    "## 2.2. What Is Algorithm Analysis?\n",
    "It is very common for beginning computer science students to compare their programs with one another. You may also have noticed that it is common for computer programs to look very similar, especially the simple ones. An interesting question often arises. When two programs solve the same problem but look different, is one program better than the other?\n",
    "\n",
    "In order to answer this question, we need to remember that there is an important difference between a program and the underlying algorithm that the program is representing. As we stated in Chapter 1, an algorithm is a generic, step-by-step list of instructions for solving a problem. It is a method for solving any instance of the problem such that given a particular input, the algorithm produces the desired result. A program, on the other hand, is an algorithm that has been encoded into some programming language. There may be many programs for the same algorithm, depending on the programmer and the programming language being used.\n",
    "\n",
    "To explore this difference further, consider the function shown in ActiveCode 1. This function solves a familiar problem, computing the sum of the first n integers. The algorithm uses the idea of an accumulator variable that is initialized to 0. The solution then iterates through the n integers, adding each to the accumulator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "def sumOfN(n):\n",
    "   theSum = 0\n",
    "   for i in range(1,n+1):\n",
    "       theSum = theSum + i\n",
    "\n",
    "   return theSum\n",
    "\n",
    "print(sumOfN(10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now look at the function in ActiveCode 2. At first glance it may look strange, but upon further inspection you can see that this function is essentially doing the same thing as the previous one. The reason this is not obvious is poor coding. We did not use good identifier names to assist with readability, and we used an extra assignment statement during the accumulation step that was not really necessary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n"
     ]
    }
   ],
   "source": [
    "def foo(tom):\n",
    "    fred = 0\n",
    "    for bill in range(1,tom+1):\n",
    "       barney = bill\n",
    "       fred = fred + barney\n",
    "\n",
    "    return fred\n",
    "\n",
    "print(foo(10))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The question we raised earlier asked whether one function is better than another. The answer depends on your criteria. The function `sumOfN` is certainly better than the function `foo` if you are concerned with readability. In fact, you have probably seen many examples of this in your introductory programming course since one of the goals there is to help you write programs that are easy to read and easy to understand.\n",
    "\n",
    "**Algorithm analysis** is concerned with comparing algorithms based upon the amount of **computing resources** that each algorithm uses. We want to be able to consider two algorithms and say that one is better than the other because it is more efficient in its use of those resources or perhaps because it simply uses fewer.\n",
    "\n",
    "At this point, it is important to think more about what we really mean by **computing resources**. There are two different ways to look at this. One way is to consider the amount of **space or memory** an algorithm requires to solve the problem.\n",
    "\n",
    "As an alternative to space requirements, we can analyze and compare algorithms based on the **amount of time** they require to execute. This measure is sometimes referred to as the “execution time” or “running time” of the algorithm. One way we can measure the execution time for the function `sumOfN` is to do a benchmark analysis. This means that we will track the actual time required for the program to compute its result. In Python, we can benchmark a function by noting the starting time and ending time with respect to the system we are using. In the `time` module there is a function called `time` that will return the current system clock time in seconds since some arbitrary starting point. By calling this function twice, at the beginning and at the end, and then computing the difference, we can get an exact number of seconds (fractions in most cases) for execution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "def sumOfN2(n):\n",
    "   start = time.time()\n",
    "\n",
    "   theSum = 0\n",
    "   for i in range(1,n+1):\n",
    "      theSum = theSum + i\n",
    "\n",
    "   end = time.time()\n",
    "\n",
    "   return theSum,end-start"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function returns a tuple consisting of the result and the amount of time (in seconds) required for the calculation. If we perform 5 invocations of the function, each computing the sum of the first 10,000 integers, we get the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sum is 50005000 required  0.0010009 seconds\n",
      "Sum is 50005000 required  0.0009995 seconds\n",
      "Sum is 50005000 required  0.0009995 seconds\n",
      "Sum is 50005000 required  0.0010002 seconds\n",
      "Sum is 50005000 required  0.0009999 seconds\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(\"Sum is %d required %10.7f seconds\" %sumOfN2(10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We discover that the time is fairly consistent and it takes on average about 0.0019 seconds to execute that code. What if we run the function adding the first 100,000 integers?\n",
    "\n",
    "Again, the time required for each run, although longer, is very consistent, averaging about 10 times more seconds. For `n` equal to 1,000,000 we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sum is 500000500000 required  0.0730007 seconds\n",
      "Sum is 500000500000 required  0.0620048 seconds\n",
      "Sum is 500000500000 required  0.0610042 seconds\n",
      "Sum is 500000500000 required  0.0620167 seconds\n",
      "Sum is 500000500000 required  0.0749931 seconds\n"
     ]
    }
   ],
   "source": [
    "for i in range(5):\n",
    "    print(\"Sum is %d required %10.7f seconds\"%sumOfN2(1000000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, the average again turns out to be about 10 times the previous.\n",
    "\n",
    "Now consider ActiveCode 3, which shows a different means of solving the summation problem. This function, `sumOfN3`, takes advantage of a closed equation $\\sum_{i=1}^{n}i=\\frac{(n)(n+1)}{2}$ to compute the sum of the first `n` integers without iterating."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sum is 50005000 required  0.0000000 seconds\n",
      "Sum is 5000050000 required  0.0000000 seconds\n",
      "Sum is 500000500000 required  0.0000000 seconds\n",
      "Sum is 50000005000000 required  0.0000000 seconds\n",
      "Sum is 5000000050000000 required  0.0000000 seconds\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "def sumOfN3(n):\n",
    "    start = time.time()\n",
    "    result = (n*(n+1))/2\n",
    "    end = time.time()\n",
    "    return result, end-start\n",
    "\n",
    "for i in [10000, 100000, 1000000, 10000000, 100000000]:\n",
    "    print(\"Sum is %d required %10.7f seconds\"%sumOfN3(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we do the same benchmark measurement for `sumOfN3`, using five different values for `n` (10,000, 100,000, 1,000,000, 10,000,000, and 100,000,000).\n",
    "\n",
    "First, the times recorded above are **shorter** than any of the previous examples. Second, they are very consistent no matter what the value of `n`. It appears that `sumOfN3` is **hardly impacted** by the number of integers being added."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But what does this benchmark really tell us? Intuitively, we can see that the iterative solutions seem to be doing more work since some program steps are being repeated. This is likely the reason it is taking longer. Also, the time required for the iterative solution seems to increase as we increase the value of `n`.\n",
    "\n",
    "We need a better way to characterize these algorithms with respect to execution time. The benchmark technique computes the actual time to execute. It does not really provide us with a useful measurement, because it is dependent on a **particular machine**, **program**, **time of day**, **compiler**, and **programming language**. Instead, we would like to have a characterization that is independent of the program or computer being used. This measure would then be useful for judging the algorithm alone and could be used to compare algorithms across implementations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3. Big-O Notation\n",
    "When trying to characterize an algorithm’s efficiency in terms of execution time, independent of any particular program or computer, it is important to quantify the number of operations or steps that the algorithm will require. If each of these steps is considered to be a basic unit of computation, then the execution time for an algorithm can be expressed as the number of steps required to solve the problem. Deciding on an appropriate basic unit of computation can be a complicated problem and will depend on how the algorithm is implemented.\n",
    "\n",
    "Computer scientists prefer to take this analysis technique one step further. It turns out that the exact number of operations is not as important as determining the most dominant part of the T(n) function. In other words, as the problem gets larger, some portion of the T(n) function tends to overpower the rest. This dominant term is what, in the end, is used for comparison. The **order of magnitude** function describes the part of T(n) that increases the fastest as the value of n increases. Order of magnitude is often called **Big-O** notation (for “order”) and written as O(f(n)). It provides a useful approximation to the actual number of steps in the computation. The function f(n) provides a simple representation of the dominant part of the original T(n).\n",
    "\n",
    "A number of very common order of magnitude functions will come up over and over as you study algorithms. These are shown in Table 1. In order to decide which of these functions is the dominant part of any T(n) function, we must see how they compare with one another as n gets large."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![big o](images/big-o.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that when n is small, the functions are not very well defined with respect to one another. It is hard to tell which is dominant. However, as n grows, there is a definite relationship and it is easy to see how they compare with one another.\n",
    "![plot](images/newplot.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.4. An Anagram Detection Example\n",
    "A good example problem for showing algorithms with different orders of magnitude is the classic anagram detection problem for strings. One string is an anagram of another if the second is simply a rearrangement of the first. For example, `'heart'` and `'earth'` are anagrams. For the sake of simplicity, we will assume that the two strings in question are of equal length and that they are made up of symbols from the set of 26 lowercase alphabetic characters. Our goal is to write a boolean function that will take two strings and return whether they are anagrams.\n",
    "### 2.4.1 Solution 1: Checking Off\n",
    "Our first solution to the anagram problem will check the lengths of the strings and then to see that each character in the first string actually occurs in the second. If it is possible to “checkoff” each character, then the two strings must be anagrams. Checking off a character will be accomplished by replacing it with the special Python value `None`. However, since strings in Python are immutable, the first step in the process will be to convert the second string to a list. Each character from the first string can be checked against the characters in the list and if found, checked off by replacement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "def anagramSolution1(s1,s2):\n",
    "    if len(s1) != len(s2):\n",
    "        stillOK = False\n",
    "\n",
    "    else:\n",
    "        alist = list(s2)\n",
    "        pos1 = 0\n",
    "        stillOK = True\n",
    "        while pos1 < len(s1) and stillOK:\n",
    "            pos2 = 0\n",
    "            found = False\n",
    "            while pos2 < len(alist) and not found:\n",
    "                if s1[pos1] == alist[pos2]:\n",
    "                    found = True\n",
    "                else:\n",
    "                    pos2 = pos2 + 1\n",
    "\n",
    "            if found:\n",
    "                alist[pos2] = None\n",
    "            else:\n",
    "                stillOK = False\n",
    "\n",
    "            pos1 = pos1 + 1\n",
    "\n",
    "    return stillOK\n",
    "\n",
    "print(anagramSolution1('abcde','dceabb'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To analyze this algorithm, we need to note that each of the n characters in `s1` will cause an iteration through up to n characters in the list from `s2`. Each of the n positions in the list will be visited once to match a character from `s1`. The number of visits then becomes the sum of the integers from 1 to n. We stated earlier that this can be written as $\\sum_{i=1}^n i=\\frac{n(n+1)}{2}$. Therefore, this solution is **O($n^2$)**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.2. Solution 2: Sort and Compare\n",
    "Another solution to the anagram problem will make use of the fact that even though `s1` and `s2` are different, they are anagrams only if they consist of exactly the same characters. So, if we begin by sorting each string alphabetically, from a to z, we will end up with the same string if the original two strings are anagrams. ActiveCode 2 shows this solution. Again, in Python we can use the built-in `sort` method on lists by simply converting each string to a list at the start."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def anagramSolution2(s1,s2):\n",
    "    alist1 = list(s1)\n",
    "    alist2 = list(s2)\n",
    "\n",
    "    alist1.sort()\n",
    "    alist2.sort()\n",
    "\n",
    "    pos = 0\n",
    "    matches = True\n",
    "\n",
    "    while pos < len(s1) and matches:\n",
    "        if alist1[pos]==alist2[pos]:\n",
    "            pos = pos + 1\n",
    "        else:\n",
    "            matches = False\n",
    "\n",
    "    return matches\n",
    "\n",
    "print(anagramSolution2('abcde','edcab'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At first glance you may be tempted to think that this algorithm is **O(n)**, since there is one simple iteration to compare the n characters after the sorting process. However, the two calls to the Python `sort` method are not without their own cost. As we will see in a later chapter, sorting is typically either **O($n^2$)** or **O($nlogn$)**, so the sorting operations dominate the iteration. In the end, this algorithm will have the same order of magnitude as that of the sorting process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.3. Solution 3: Brute Force\n",
    "A **brute force** technique for solving a problem typically tries to exhaust all possibilities. For the anagram detection problem, we can simply generate a list of all possible strings using the characters from `s1` and then see if `s2` occurs. However, there is a difficulty with this approach. When generating all possible strings from s1, there are n possible first characters, $n−1$ possible characters for the second position, $n−2$ for the third, and so on. The total number of candidate strings is $n∗(n−1)∗(n−2)∗...∗3∗2∗1$, which is n!. Although some of the strings may be duplicates, the program cannot know this ahead of time and so it will still generate n! different strings.\n",
    "\n",
    "It turns out that $n!$\n",
    "grows even faster than $2n$ as $n$ gets large. In fact, if `s1` were 20 characters long, there would be $20!=2,432,902,008,176,640,000$ possible candidate strings. If we processed one possibility every second, it would still take us 77,146,816,596 years to go through the entire list. This is probably not going to be a good solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4.4. Solution 4: Count and Compare\n",
    "Our final solution to the anagram problem takes advantage of the fact that any two anagrams will have the same number of a’s, the same number of b’s, the same number of c’s, and so on. In order to decide whether two strings are anagrams, we will first count the number of times each character occurs. Since there are 26 possible characters, we can use a list of 26 counters, one for each possible character. Each time we see a particular character, we will increment the counter at that position. In the end, if the two lists of counters are identical, the strings must be anagrams. ActiveCode 3 shows this solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def anagramSolution4(s1,s2):\n",
    "    c1 = [0]*26\n",
    "    c2 = [0]*26\n",
    "\n",
    "    for i in range(len(s1)):\n",
    "        pos = ord(s1[i])-ord('a')\n",
    "        c1[pos] = c1[pos] + 1\n",
    "\n",
    "    for i in range(len(s2)):\n",
    "        pos = ord(s2[i])-ord('a')\n",
    "        c2[pos] = c2[pos] + 1\n",
    "\n",
    "    j = 0\n",
    "    stillOK = True\n",
    "    while j<26 and stillOK:\n",
    "        if c1[j]==c2[j]:\n",
    "            j = j + 1\n",
    "        else:\n",
    "            stillOK = False\n",
    "\n",
    "    return stillOK\n",
    "\n",
    "print(anagramSolution4('apple','pleap'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, the solution has a number of iterations. However, unlike the first solution, none of them are nested. The first two iterations used to count the characters are both based on n. The third iteration, comparing the two lists of counts, always takes 26 steps since there are 26 possible characters in the strings. Adding it all up gives us $T(n)=2n+26$ steps. That is **O(n)**. We have found a linear order of magnitude algorithm for solving this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before leaving this example, we need to say something about space requirements. Although the last solution was able to run in linear time, it could only do so by using additional storage to keep the two lists of character counts. In other words, this algorithm sacrificed space in order to gain time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Self Check**\n",
    "\n",
    ">Q-1: Given the following code fragment, what is its Big-O running time?\n",
    ">>\n",
    "    test = 0\n",
    "    for i in range(n):\n",
    "       for j in range(n):\n",
    "          test = test + i * j\n",
    ">> * A. O(n)\n",
    ">> * B. O($n^2$)\n",
    ">> * C. O($log n$)\n",
    ">> * D. O($n^3$)\n",
    "\n",
    "> Q-2: Given the following code fragment what is its Big-O running time?\n",
    ">>  \n",
    "    test = 0\n",
    "    for i in range(n):\n",
    "       test = test + 1\n",
    "    for j in range(n):\n",
    "       test = test - 1\n",
    ">> * A. O(n)\n",
    ">> * B. O($n^2$)\n",
    ">> * C. O($log n$)\n",
    ">> * D. O($n^3$)\n",
    "\n",
    "> Q-3: Given the following code fragment what is its Big-O running time?\n",
    ">>\n",
    "    i = n\n",
    "    while i > 0:\n",
    "       k = 2 + 2\n",
    "       i = i // 2\n",
    ">> * A. O(n)\n",
    ">> * B. O($n^2$)\n",
    ">> * C. O($log n$)\n",
    ">> * D. O($n^3$)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.5. Performance of Python Data Structures\n",
    "Now that you have a general idea of Big-O notation and the differences between the different functions, our goal in this section is to tell you about the Big-O performance for the operations on Python lists and dictionaries. We will then show you some timing experiments that illustrate the costs and benefits of using certain operations on each data structure. It is important for you to understand the efficiency of these Python data structures because they are the building blocks we will use as we implement other data structures in the remainder of the book. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.6. Lists\n",
    "Two common operations are indexing and assigning to an index position. Both of these operations take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list they are $O(1)$.\n",
    "\n",
    "Let’s look at four different ways we might generate a list of `n` numbers starting with 0. First we’ll try a `for` loop and create the list by concatenation, then we’ll use append rather than concatenation. Next, we’ll try creating the list using list comprehension and finally, and perhaps the most obvious way, using the range function wrapped by a call to the list constructor. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test1():\n",
    "    l = []\n",
    "    for i in range(1000):\n",
    "        l = l + [i]\n",
    "\n",
    "def test2():\n",
    "    l = []\n",
    "    for i in range(1000):\n",
    "        l.append(i)\n",
    "\n",
    "def test3():\n",
    "    l = [i for i in range(1000)]\n",
    "\n",
    "def test4():\n",
    "    l = list(range(1000))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To capture the time it takes for each of our functions to execute we will use Python’s `timeit` module. The `timeit` module is designed to allow Python developers to make cross-platform timing measurements by running functions in a consistent environment and using timing mechanisms that are as similar as possible across operating systems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "concat  0.7061420559984981 milliseconds\n",
      "append  0.03678335700533353 milliseconds\n",
      "comprehension  0.019735926005523652 milliseconds\n",
      "list range  0.008588958000473212 milliseconds\n"
     ]
    }
   ],
   "source": [
    "    \n",
    "import timeit\n",
    "\n",
    "t1 = timeit.Timer(\"test1()\", \"from __main__ import test1\")\n",
    "print(\"concat \",t1.timeit(number=1000), \"milliseconds\")\n",
    "\n",
    "t2 = timeit.Timer(\"test2()\", \"from __main__ import test2\")\n",
    "print(\"append \",t2.timeit(number=1000), \"milliseconds\")\n",
    "\n",
    "t3 = timeit.Timer(\"test3()\", \"from __main__ import test3\")\n",
    "print(\"comprehension \",t3.timeit(number=1000), \"milliseconds\")\n",
    "\n",
    "t4 = timeit.Timer(\"test4()\", \"from __main__ import test4\")\n",
    "print(\"list range \",t4.timeit(number=1000), \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the experiment above the statement that we are timing is the function call to `test1()`, `test2()`, and so on. The setup statement may look very strange to you, so let’s consider it in more detail. You are probably very familiar with the `from`, `import` statement, but this is usually used at the beginning of a Python program file. In this case the statement from `__main__ import test1` imports the function `test1` from the `__main__` namespace into the namespace that `timeit` sets up for the timing experiment. The `timeit` module does this because it wants to run the timing tests in an environment that is uncluttered by any stray variables you may have created, that may interfere with your function’s performance in some unforeseen way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above experiment we also show the times for two additional methods for creating a list; using the list constructor with a call to `range` and a list comprehension. It is interesting to note that the list comprehension is twice as fast as a `for` loop with an `append` operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When pop is called on the end of the list it takes $O(1)$ but when pop is called on the first element in the list or anywhere in the middle it is $O(n)$. The reason for this lies in how Python chooses to implement lists. When an item is taken from the front of the list, in Python’s implementation, all the other elements in the list are shifted one position closer to the beginning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|     Operation    | Big-O Efficiency |\n",
    "|:----------------:|:----------------:|\n",
    "| index []         | O(1)             |\n",
    "| index assignment | O(1)             |\n",
    "| append           | O(1)             |\n",
    "| pop()            | O(1)             |\n",
    "| pop(i)           | O(n)             |\n",
    "| insert(i,item)   | O(n)             |\n",
    "| del operator     | O(n)             |\n",
    "| iteration        | O(n)             |\n",
    "| contains (in)    | O(n)             |\n",
    "| get slice [x:y]  | O(k)             |\n",
    "| del slice        | O(n)             |\n",
    "| set slice        | O(n+k)           |\n",
    "| reverse          | O(n)             |\n",
    "| concatenate      | O(k)             |\n",
    "| sort             | O(n log n)       |\n",
    "| multiply         | O(nk)            |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a couple of things to notice about Listing 4. The first is the statement `from __main__ import x`. Although we did not define a function we do want to be able to use the list object x in our test. This approach allows us to time just the single `pop` statement and get the most accurate measure of the time for that single operation. Because the timer repeats 1000 times it is also important to point out that the list is decreasing in size by 1 each time through the loop. But since the initial list is two million elements in size we only reduce the overall size by 0.05%."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "popzero= 2.385986116998538\n",
      "popend= 3.0216004233807325e-05\n"
     ]
    }
   ],
   "source": [
    "popzero = timeit.Timer(\"x.pop(0)\",\n",
    "                       \"from __main__ import x\")\n",
    "popend = timeit.Timer(\"x.pop()\",\n",
    "                      \"from __main__ import x\")\n",
    "\n",
    "x = list(range(2000000))\n",
    "print('popzero= '+ str(popzero.timeit(number=1000)))\n",
    "\n",
    "x = list(range(2000000))\n",
    "print('popend= '+ str(popend.timeit(number=1000)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While our first test does show that `pop(0)` is indeed slower than `pop()`, it does not validate the claim that `pop(0)` is $O(n)$ while `pop()` is $O(1)$. To validate that claim we need to look at the performance of both calls over a range of list sizes. Listing 5 implements this test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pop(0)   pop()\n",
      "        1.21857,         0.00005\n",
      "        2.35087,         0.00003\n",
      "        3.67533,         0.00004\n",
      "        5.21022,         0.00003\n",
      "        5.82891,         0.00004\n",
      "        7.20785,         0.00003\n",
      "        8.21227,         0.00003\n",
      "        9.81002,         0.00003\n",
      "       10.49910,         0.00003\n",
      "       11.64561,         0.00004\n",
      "       12.94542,         0.00003\n",
      "       14.00856,         0.00003\n",
      "       15.14190,         0.00003\n",
      "       16.29091,         0.00003\n",
      "       17.94550,         0.00003\n",
      "       18.63541,         0.00003\n",
      "       19.82718,         0.00003\n",
      "       21.26889,         0.00003\n",
      "       22.83129,         0.00003\n",
      "       25.58670,         0.00003\n",
      "       27.80128,         0.00010\n",
      "       30.36162,         0.00006\n",
      "       27.12849,         0.00003\n",
      "       32.22194,         0.00003\n",
      "       31.67308,         0.00010\n",
      "       36.36844,         0.00003\n",
      "       32.48421,         0.00004\n",
      "       35.71271,         0.00005\n",
      "       34.50717,         0.00005\n",
      "       36.60606,         0.00003\n",
      "       37.30606,         0.00006\n",
      "       41.63544,         0.00003\n",
      "       39.93579,         0.00003\n",
      "       41.84497,         0.00004\n",
      "       45.34707,         0.00005\n",
      "       45.46922,         0.00010\n",
      "       45.01541,         0.00004\n"
     ]
    }
   ],
   "source": [
    "popzero = timeit.Timer(\"x.pop(0)\",\n",
    "                \"from __main__ import x\")\n",
    "popend = timeit.Timer(\"x.pop()\",\n",
    "               \"from __main__ import x\")\n",
    "print(\"pop(0)   pop()\")\n",
    "for i in range(1000000,100000001,1000000):\n",
    "    x = list(range(i))\n",
    "    pt = popend.timeit(number=1000)\n",
    "    x = list(range(i))\n",
    "    pz = popzero.timeit(number=1000)\n",
    "    #print(\"%15.5f, %15.5f\" %(pz,pt))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.7. Dictionaries\n",
    "The second major Python data structure is the dictionary. As you probably recall, dictionaries differ from lists in that you can access items in a dictionary by a key rather than a position. Later in this book you will see that there are many ways to implement a dictionary. The thing that is most important to notice right now is that the get item and set item operations on a dictionary are $O(1)$. Another important dictionary operation is the contains operation. Checking to see whether a key is in the dictionary or not is also $O(1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|   operation   | Big-O Efficiency |\n",
    "|:-------------:|:----------------:|\n",
    "| copy          | O(n)             |\n",
    "| get item      | O(1)             |\n",
    "| set item      | O(1)             |\n",
    "| delete item   | O(1)             |\n",
    "| contains (in) | O(1)             |\n",
    "| iteration     | O(n)             |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For our last performance experiment we will compare the performance of the contains operation between **lists** and **dictionaries**. In the process we will confirm that the contains operator for lists is $O(n)$ and the contains operator for dictionaries is $O(1)$. The experiment we will use to compare the two is simple. We’ll make a list with a range of numbers in it. Then we will pick numbers at random and check to see if the numbers are in the list. If our performance tables are correct the bigger the list the longer it should take to determine if any one number is contained in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000,     0.039,     0.000\n",
      "30000,     0.103,     0.000\n",
      "50000,     0.153,     0.001\n",
      "70000,     0.210,     0.001\n",
      "90000,     0.279,     0.001\n",
      "110000,     0.355,     0.001\n",
      "130000,     0.423,     0.001\n",
      "150000,     0.545,     0.001\n",
      "170000,     0.564,     0.001\n",
      "190000,     0.653,     0.001\n",
      "210000,     0.688,     0.001\n",
      "230000,     0.803,     0.001\n",
      "250000,     0.876,     0.001\n",
      "270000,     0.947,     0.001\n",
      "290000,     1.069,     0.001\n",
      "310000,     1.129,     0.001\n",
      "330000,     1.126,     0.001\n",
      "350000,     1.201,     0.001\n",
      "370000,     1.271,     0.001\n",
      "390000,     1.413,     0.001\n",
      "410000,     1.497,     0.001\n",
      "430000,     1.539,     0.001\n",
      "450000,     1.585,     0.001\n",
      "470000,     1.668,     0.001\n",
      "490000,     1.692,     0.001\n",
      "510000,     1.765,     0.001\n",
      "530000,     2.035,     0.001\n",
      "550000,     1.851,     0.001\n",
      "570000,     1.917,     0.001\n",
      "590000,     2.061,     0.001\n",
      "610000,     2.206,     0.001\n",
      "630000,     2.213,     0.001\n",
      "650000,     2.256,     0.001\n",
      "670000,     2.274,     0.001\n",
      "690000,     2.441,     0.001\n",
      "710000,     2.554,     0.001\n",
      "730000,     2.846,     0.001\n",
      "750000,     2.755,     0.001\n",
      "770000,     2.912,     0.001\n",
      "790000,     2.929,     0.001\n",
      "810000,     2.863,     0.001\n",
      "830000,     2.892,     0.001\n",
      "850000,     3.211,     0.001\n",
      "870000,     3.049,     0.001\n",
      "890000,     3.122,     0.001\n",
      "910000,     3.153,     0.001\n",
      "930000,     3.241,     0.001\n",
      "950000,     3.435,     0.001\n",
      "970000,     3.415,     0.001\n",
      "990000,     3.421,     0.001\n"
     ]
    }
   ],
   "source": [
    "import timeit\n",
    "import random\n",
    "\n",
    "for i in range(10000,1000001,20000):\n",
    "    t = timeit.Timer(\"random.randrange(%d) in x\"%i,\n",
    "                     \"from __main__ import random,x\")\n",
    "    x = list(range(i))\n",
    "    lst_time = t.timeit(number=1000)\n",
    "    x = {j:None for j in range(i)}\n",
    "    d_time = t.timeit(number=1000)\n",
    "    print(\"%d,%10.3f,%10.3f\" % (i, lst_time, d_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![dic](images/listvdict.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since Python is an evolving language, there are always changes going on behind the scenes. The latest information on the performance of Python data structures can be found on the Python website. As of this writing the Python wiki has a nice time complexity page that can be found at the [Time Complexity Wiki](https://wiki.python.org/moin/TimeComplexity)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.8. Summary\n",
    "\n",
    "* Algorithm analysis is an implementation-independent way of measuring an algorithm.\n",
    "* Big-O notation allows algorithms to be classified by their dominant process with respect to the size of the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.9. Key Terms\n",
    "\n",
    "| Key          | key             | Key                |\n",
    "|--------------|-----------------|--------------------|\n",
    "| average case | Big-O notation  | brute force        |\n",
    "| checking off | exponential     | linear             |\n",
    "| log linear   | logarithmic     | order of magnitude |\n",
    "| quadratic    | time complexity | worst case         |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.10. Discussion Questions\n",
    "\n",
    "1. Give the Big-O performance of the following code fragment:\n",
    "\n",
    "    \n",
    "    for i in range(n):\n",
    "       for j in range(n):\n",
    "          k = 2 + 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Give the Big-O performance of the following code fragment:\n",
    "\n",
    "\n",
    "    for i in range(n):\n",
    "         k = 2 + 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Give the Big-O performance of the following code fragment:\n",
    "\n",
    "\n",
    "    i = n\n",
    "    while i > 0:\n",
    "       k = 2 + 2\n",
    "       i = i // 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Give the Big-O performance of the following code fragment:\n",
    "\n",
    "\n",
    "    for i in range(n):\n",
    "       for j in range(n):\n",
    "          for k in range(n):\n",
    "             k = 2 + 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Give the Big-O performance of the following code fragment:\n",
    "\n",
    "\n",
    "    for i in range(n):\n",
    "       k = 2 + 2\n",
    "    for j in range(n):\n",
    "       k = 2 + 2\n",
    "    for k in range(n):\n",
    "       k = 2 + 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.11. Programming Exercises\n",
    "1. Devise an experiment to verify that the list index operator is $O(1)$\n",
    "2. Devise an experiment to verify that get item and set item are $O(1)$ for dictionaries.\n",
    "3. Devise an experiment that compares the performance of the `del` operator on lists and dictionaries.\n",
    "4. Given a list of numbers in random order, write an algorithm that works in $O(nlog(n))$ to find the kth smallest number in the list.\n",
    "5. Can you improve the algorithm from the previous problem to be linear? Explain."
   ]
  },
  {
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}