week08_complexity_with_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Computational complexity\n",
    "\n",
    "Computational complexity is concerned with describing the amount of resources needed to run an algorithm. Most\n",
    "of the time the resource that we are interested in is time, but other types of resources (such as the amount of\n",
    "memory required) can be analyzed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The size of a problem\n",
    "\n",
    "Complexity is normally expressed as a function $f(n)$, or sometimes $T(n)$(especially for recursive algorithms),\n",
    "called a *timing function* where $n$ is the size of the inputs to the algorithm. As\n",
    "with recursion, the size of the inputs is technically defined to be the number of bits needed to specify the\n",
    "inputs, but we will typically use a less precise measure of the size that depends on the types of inputs to the\n",
    "algorithm. For example, for algorithms whose input is a list we will typically use the number of elements in the\n",
    "list as the size of the input."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Number of operations versus time\n",
    "\n",
    "Specifying the amount of time needed to run an algorithm is not generally useful because the amount of time depends\n",
    "strongly on the exact configuration of the computer running the algorithm. Instead, the time complexity of an\n",
    "algorithm is expressed as a function of the number of elementary operations required by the algorithm.\n",
    "\n",
    "An elementary operation is an operation that requires an amount of time to complete that is independent of the\n",
    "size of the problem. People who study complexity theory assume that elementary operations require a constant\n",
    "amount of time.\n",
    "\n",
    "The following is a list of operations that we will consider to be elementary operations:\n",
    "\n",
    "- arithmetic operators `+`, `-`, `*`, `/`, `//`, `%`, `**` involving integer or floating-point values\n",
    "    - String concatenation (e.g., `'hello ' + 'world'`) is not an elementary operation. In concatenation,\n",
    "    Python creates a new string by copying the characters from the strings; thus, the number of operations\n",
    "    is proportional to the length of the two strings\n",
    "- comparison operators `>`, `>=`,`<`, `<=`, `==`, `!=`\n",
    "- loop control (`for` statement)\n",
    "- the act of branching in an `if` statement \n",
    "    - evaluating the branch condition is not necessarily a constant time operation\n",
    "- getting or setting a single value in a sequence using an integer index\n",
    "- the act of assigning a value to a variable\n",
    "    - evaluating the right-hand side of an assignment statement is not necessarily a constant time operation\n",
    "- `break`, `continue` statements\n",
    "- the act of returning a value from a function\n",
    "    - evaluating the value returned in a `return` statement is not necessarily a constant time \n",
    "- the act of calling a function\n",
    "    \n",
    "An example of a branch condition in an `if` statement that is not a constant operation is:\n",
    "\n",
    "```python\n",
    "# t is a list of strings\n",
    "if 'hello' in t:\n",
    "```\n",
    "\n",
    "because `in` potentially tests all $n$ elements of the list for equality to `'hello'`.\n",
    "\n",
    "An example of evaluating the right-hand side of an assignment statement that is not a constant operation is:\n",
    "\n",
    "```python\n",
    "# t is a list of numeric values\n",
    "s = sum(t)\n",
    "```\n",
    "\n",
    "because the function `sum` computes the sum of all $n$ elements in the list.\n",
    "\n",
    "An example of evaluating the value returned in a `return` statement that is not a constant operation is:\n",
    "\n",
    "```python\n",
    "# s is the input string to the function\n",
    "return s + '!'\n",
    "```\n",
    "\n",
    "because using `+` to concatenate `s` with `!` causes Python to make a new string by copying the $n$ characters\n",
    "from `s` and then appending the `!` to the end of the copied string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Timing functions\n",
    "\n",
    "To determine the timing function for an algorithm we count the number of elementary operations as a function of\n",
    "the size of the input.\n",
    "\n",
    "### Example 1\n",
    "\n",
    "Consider a function that swaps two elements of a list:\n",
    "\n",
    "```python\n",
    "def swap(t, i1, i2):\n",
    "    tmp = t[i1]\n",
    "    t[i1] = t[i2]\n",
    "    t[i2] = tmp\n",
    "```\n",
    "\n",
    "To derive the timing function we begin by counting the number of elementary operations on each line of the\n",
    "function:\n",
    "\n",
    "```python\n",
    "def swap(t, i1, i2):        NUMBER OF ELEM OPS\n",
    "    tmp = t[i1]             2 (1 element access using an index, 1 assignment)\n",
    "    t[i1] = t[i2]           3 (2 element accesses using an index, 1 assignment)\n",
    "    t[i2] = tmp             2 (1 element access using an index, 1 assignment)\n",
    "```\n",
    "\n",
    "We then determine how many times each line of the function runs when the function is called:\n",
    "\n",
    "```python\n",
    "def swap(t, i1, i2):        NUMBER OF TIMES A LINE IS RUN\n",
    "    tmp = t[i1]             1\n",
    "    t[i1] = t[i2]           1\n",
    "    t[i2] = tmp             1\n",
    "```\n",
    "\n",
    "In this example, there are no branching or looping statements so each line of code runs once.\n",
    "\n",
    "The timing function is obtained by multiplying the number of elementary operations per line by the number of\n",
    "times the line is run and summing the terms:\n",
    "\n",
    "```python\n",
    "def swap(t, i1, i2):        \n",
    "    tmp = t[i1]             2 * 1\n",
    "    t[i1] = t[i2]           3 * 1\n",
    "    t[i2] = tmp             2 * 1\n",
    "```\n",
    "\n",
    "which yields $f(n) = 7$. In other words, running `swap` requires $7$ elementary operations (notice that $f(n)$ is\n",
    "independent of the size $n$ of the list in this example)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 1** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def is_even(n):\n",
    "    boo = n % 2 == 0\n",
    "    return boo\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 1** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def is_even(n):\n",
    "    boo = n % 2 == 0       3 * 1 (1 arithmetic operation, 1 comparison operation, 1 assignment operation)\n",
    "    return boo             1 * 1 (1 return statement)\n",
    "```\n",
    "\n",
    "$f(n) = 4$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2\n",
    "\n",
    "Consider a simple loop that sums the elements of a list `t` of length `n`:\n",
    "\n",
    "```python\n",
    "def my_sum(t):\n",
    "    sum = 0;\n",
    "    for elem in t:\n",
    "        sum = sum + t[i]\n",
    "```\n",
    "\n",
    "To derive the timing function we begin by counting the number of elementary operations on each line of the\n",
    "function:\n",
    "\n",
    "```python\n",
    "def my_sum(t):                        NUMBER OF OPERATIONS\n",
    "    sum = 0;                          1\n",
    "    for elem in t:                    1 (loop control)\n",
    "        sum = sum + t[i]              3 (1 element access using an index, 1 addition, 1 assignment)\n",
    "```\n",
    "\n",
    "Here we count the operations hidden by the `for` statement as one elementary operation although in reality\n",
    "there are multiple elementary operations involved in the loop control.\n",
    "\n",
    "We then determine how many times each line of the function runs when the function is called:\n",
    "\n",
    "```python\n",
    "def my_sum(t):                        NUMBER OF TIMES LINE IS RUN\n",
    "    sum = 0;                          1\n",
    "    for elem in t:                    1\n",
    "        sum = sum + t[i]              n (once for each iteration of the loop)\n",
    "```\n",
    "\n",
    "Here we count the `for` statement as only running once although in reality parts of the loop control statement\n",
    "will run $n$ times.\n",
    "\n",
    "The overall timing function is $f(n) = 3n + 2$ which does depend on the size $n$ of the list."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 2** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def alternating_sum(t):\n",
    "    # computes t[0] - t[1] + t[2] - t[3] + t[4] ...\n",
    "    n = len(t)\n",
    "    result = 0\n",
    "    for i in range(0, n, 2):\n",
    "        result = result + t[i]\n",
    "    for i in range(1, n, 2):\n",
    "        result = result - t[i]\n",
    "    return result\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 2** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def alternating_sum(t):\n",
    "    # computes t[0] - t[1] + t[2] - t[3] + t[4] ...\n",
    "    n = len(t)                    2 * 1 (1 function call, 1 assignment)\n",
    "    result = 0                    1 * 1 (1 assignment)\n",
    "    for i in range(0, n, 2):      1 * 1 (1 loop control)\n",
    "        result = result + t[i]    3 * n / 2 (1 addition, 1 list access, 1 assignment run n / 2 times)\n",
    "    for i in range(1, n, 2):      1 * 1 (1 loop control)\n",
    "        result = result - t[i]    3 * n / 2 (1 addition, 1 list access, 1 assignment run n / 2 times)\n",
    "    return result                 1 * 1 (1 return)\n",
    "```\n",
    "\n",
    "$f(n) = 3n + 6$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 3** Derive the timing function for the following Python function; notice that this function computes\n",
    "the same value as the previous question.\n",
    "\n",
    "```python\n",
    "def alternating_sum2(t):\n",
    "    # computes t[0] - t[1] + t[2] - t[3] + t[4] ...\n",
    "    n = len(t)\n",
    "    result = 0\n",
    "    sign = 1\n",
    "    for i in range(0, n):\n",
    "        result = result + sign * t[i]\n",
    "        sign = -sign\n",
    "    return result\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 3** Derive the timing function for the following Python function; notice that this function computes\n",
    "the same value as the previous question.\n",
    "\n",
    "```python\n",
    "def alternating_sum2(t):\n",
    "    # computes t[0] - t[1] + t[2] - t[3] + t[4] ...\n",
    "    n = len(t)                            2 * 1 (1 function call, 1 assignment)\n",
    "    result = 0                            1 * 1 (1 assignment)\n",
    "    sign = 1                              1 * 1 (1 assignment)\n",
    "    for i in range(0, n):                 1 * 1 (1 loop control)\n",
    "        result = result + sign * t[i]     4 * n (1 addition, 1 multiplication, 1 list access, 1 assignment run n times)\n",
    "        sign = -sign                      2 * n (1 negation, 1 assignment run n times)\n",
    "    return result                         1 * 1 (1 return)\n",
    "```\n",
    "\n",
    "$f(n) = 6n + 6$ which is the same as Exercise 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 4** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def variance(t):\n",
    "    # computes the variance of the elements in t\n",
    "    n = len(t)\n",
    "    mean = my_sum(t) / n\n",
    "    var = 0\n",
    "    for elem in t:\n",
    "        var = var + (elem - mean) ** 2\n",
    "    var = var / (n - 1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 4** Derive the timing function for the following Python function:\n",
    "\n",
    "This exercise should have appeared near the end of the notebook because the solution requires knowing what\n",
    "to do when a function calls another function.\n",
    "\n",
    "```python\n",
    "def variance(t):\n",
    "    # computes the variance of the elements in t\n",
    "    n = len(t)                           2 * 1 (1 function call, 1 assignment)\n",
    "    mean = my_sum(t) / n                 (O(n) + 2) * 1 (my_sum is in O(n), 1 division, 1 assignment)\n",
    "    var = 0                              1 * 1 (1 assignment)\n",
    "    for elem in t:                       1 * 1 (loop control)\n",
    "        var = var + (elem - mean) ** 2   4 * n (1 addition, 1 subtraction, 1 exponentiation, 1 assignment run n times)\n",
    "    var = var / (n - 1)                  3 * 1 (1 division, 1 subtraction, 1 assignment)\n",
    "```\n",
    "\n",
    "$f(n) = 5n + 9$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 3\n",
    "\n",
    "Consider a simple loop that finds the maximum element in a non-empty list `t` of length `n`:\n",
    "\n",
    "```python\n",
    "def my_max(t):\n",
    "    max_val = t[0];\n",
    "    for i in range(1, len(t)):\n",
    "        ti = t[i]\n",
    "        if ti > max_val:\n",
    "            max_val = ti\n",
    "    return max_val\n",
    "```\n",
    "\n",
    "For simplicity, we have not performed any input validation (test if `t` is empty).\n",
    "\n",
    "To derive the timing function we begin by counting the number of elementary operations on each line of the\n",
    "function:\n",
    "\n",
    "```python\n",
    "def my_max(t):                        NUMBER OF OPERATIONS\n",
    "    max_val = t[0]                    2 (1 element access using an index, 1 assignment)\n",
    "    for i in range(1, len(t)):        1 (loop control)\n",
    "        ti = t[i]                     2 (1 element access using an index, 1 assignment)\n",
    "        if ti > max_val:              2 (1 if, 1 comparison)\n",
    "            max_val = ti              1 (1 assignment)\n",
    "    return max_val                    1 (1 return)\n",
    "```\n",
    "\n",
    "We then determine how many times each line of the function runs when the function is called:\n",
    "\n",
    "```python\n",
    "def my_max(t):                        NUMBER OF TIMES LINE IS RUN\n",
    "    max_val = t[0]                    1\n",
    "    for i in range(1, len(t)):        1\n",
    "        ti = t[i]                     n - 1\n",
    "        if ti > max_val:              n - 1\n",
    "            max_val = ti              between 0 and n - 1\n",
    "    return max_val                    1\n",
    "```\n",
    "\n",
    "Notice that the `if` statement makes it impossible to accurately count how many times `max_val = ti` runs\n",
    "because that number depends on the relative ordering of the elements of `t`. If the elements of `t` are arranged\n",
    "in increasing order, then `max_val = ti` runs $n-1$ times. If the elements of `t` are arranged\n",
    "in decreasing order, then `max_val = ti` runs $0$ times. If the elements of `t` are arranged in some non-sorted\n",
    "order then `max_val = ti` runs somewhere between $0$ and $n-1$ times.\n",
    "\n",
    "In complexity analysis, we are often concerned with the worst-case complexity. To derive the worst-case\n",
    "complexity of `my_max` we assume that a line of code that might run does in fact run; thus, we assume that\n",
    "`max_val = ti` runs once each time the loop runs. With this assumption, the timing function for `my_max` is\n",
    "\n",
    "$$\\begin{align}\n",
    "f(n) & =  2 + 1 + 2(n - 1) + 2(n-1) + 1(n-1) + 1\\\\\n",
    "& = 5n - 1\n",
    "\\end{align}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 5** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    for elem in t:\n",
    "        if elem == val:\n",
    "            return True\n",
    "    return False\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 5** Derive the timing function for the following Python function:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    for elem in t:               1 * 1\n",
    "        if elem == val:          2 * n (1 comparison, 1 if run at most n times)\n",
    "            return True          1 * 1 (return statement can only run once)\n",
    "    return False                 1 * 1\n",
    "```\n",
    "\n",
    "$f(n) = 2n + 3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 6** Derive the timing function for the following slightly different version of `contains`:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    boo = False\n",
    "    for elem in t:\n",
    "        if elem == val:\n",
    "            boo = True\n",
    "    return boo\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 6** Derive the timing function for the following slightly different version of `contains`:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    boo = False                 1 * 1\n",
    "    for elem in t:              1 * 1\n",
    "        if elem == val:         2 * n (1 comparison, 1 if run at most n times)\n",
    "            boo = True          1 * n (1 assignment run at most n times)\n",
    "    return boo                  1 * 1\n",
    "```\n",
    "\n",
    "$f(n) = 3n + 3$. Notice that this function does $n$ operations more work than the equivalent function in Exercise 5 because it does not terminate the loop with a return statement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 7** Derive the timing function for the following slightly different version of `contains`:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    boo = False\n",
    "    for elem in t:\n",
    "        if elem == val:\n",
    "            boo = True\n",
    "            break\n",
    "    return boo\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 7** Derive the timing function for the following slightly different version of `contains`:\n",
    "\n",
    "```python\n",
    "def contains(t, val):\n",
    "    boo = False                1 * 1\n",
    "    for elem in t:             1 * 1\n",
    "        if elem == val:        2 * n\n",
    "            boo = True         1 * 1 (different than Exercise 6 because of the break statement)\n",
    "            break              1 * 1 \n",
    "    return boo                 1 * 1\n",
    "```\n",
    "\n",
    "$f(n) = 2n + 5$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 4\n",
    "\n",
    "Suppose that you have two lists of the same length $n$ and you want to determine if every element in\n",
    "the first list is also in the second list. A function that solves this problem is:\n",
    "\n",
    "```python\n",
    "def have_common_elements(s, t):\n",
    "    # assumes s and t are non-empty and have the same length\n",
    "    for elem_s in s:\n",
    "        has_elem_s = False\n",
    "        for elem_t in t:\n",
    "            if elem_s == elem_t:\n",
    "                has_elem_s = True\n",
    "        if not has_elem_s:\n",
    "            return False\n",
    "    return True\n",
    "```\n",
    "\n",
    "To derive the timing function we begin by counting the number of elementary operations on each line of the\n",
    "function:\n",
    "\n",
    "```python\n",
    "def have_common_elements(s, t):                NUMBER OF OPERATIONS\n",
    "    # assumes s and t are non-empty and have the same length\n",
    "    for elem_s in s:                           1\n",
    "        has_elem_s = False                     1\n",
    "        for elem_t in t:                       1\n",
    "            if elem_s == elem_t:               2\n",
    "                has_elem_s = True              1\n",
    "        if not has_elem_s:                     2 (1 if, 1 not)\n",
    "            return False                       1\n",
    "    return True                                1\n",
    "```\n",
    "\n",
    "We then determine how many times each line of the function runs when the function is called:\n",
    "\n",
    "```python\n",
    "def have_common_elements(s, t):                NUMBER OF TIMES LINE IS RUN\n",
    "    # assumes s and t are non-empty and have the same length\n",
    "    for elem_s in s:                           1\n",
    "        has_elem_s = False                     n\n",
    "        for elem_t in t:                       n\n",
    "            if elem_s == elem_t:               n * n\n",
    "                has_elem_s = True              n * n\n",
    "        if not has_elem_s:                     n\n",
    "            return False                       1\n",
    "    return True                                1\n",
    "```\n",
    "\n",
    "Notice that the line `if elem_s == elem_t:` runs $n^2$ times because it is inside of loop (`for elem_t in t`)\n",
    "that is inside of another loop (`for elem_s in s`) and both loops run $n$ times.\n",
    "\n",
    "The timing function for `have_common_elements` is\n",
    "\n",
    "$$\\begin{align}\n",
    "f(n) & =  1 + n + n + 2n^2 + 1n^2 + 2n + 1 + 1 \\\\\n",
    "& = 3n^2 + 4n + 3\n",
    "\\end{align}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 8** The set union problem can be stated as follows: Given two lists `s` and `t` where `s` has no \n",
    "duplicate elements and `t` has no duplicate elements, compute the list `u` of elements made up of all the elements\n",
    "of `s` and `t` such that `u` has no duplicate elements. Derive the timing function for the following\n",
    "implementation of a set union function assuming `s` and `t` both have `n` elements:\n",
    "\n",
    "```python\n",
    "def union(s, t):\n",
    "    u = s[:]\n",
    "    for elem_t in t:\n",
    "        include = True\n",
    "        for elem_s in s:\n",
    "            if elem_s == elem_t:\n",
    "                include = False\n",
    "                break\n",
    "        if include:\n",
    "            u.append(elem_t)\n",
    "    return u\n",
    "```\n",
    "\n",
    "Assume that `append(elem_t)` is an elementary operation (which is actually true most of the time)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 8** The set union problem can be stated as follows: Given two lists `s` and `t` where `s` has no \n",
    "duplicate elements and `t` has no duplicate elements, compute the list `u` of elements made up of all the elements\n",
    "of `s` and `t` such that `u` has no duplicate elements. Derive the timing function for the following\n",
    "implementation of a set union function assuming `s` and `t` both have `n` elements:\n",
    "\n",
    "```python\n",
    "def union(s, t):\n",
    "    u = s[:]                         1 * n (at least n operations needed to copy s)\n",
    "    for elem_t in t:                 1 * 1\n",
    "        include = True               1 * n\n",
    "        for elem_s in s:             1 * n (runs n times because of the outer loop)\n",
    "            if elem_s == elem_t:     2 * n * n (runs at most n * n times because of the nested loop)\n",
    "                include = False      1 * n (runs once each time the inner loop runs, and the inner loop runs n times\n",
    "                break                1 * 1\n",
    "        if include:                  1 * n (runs once each time the outer loop runs)\n",
    "            u.append(elem_t)         1 * n (runs at most once each time the outer loop runs)\n",
    "    return u                         1 * 1\n",
    "```\n",
    "\n",
    "$f(n) = 2n^2 + 6n + 3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 9** Derive the timing function for the following Python function that tests if a list contains any\n",
    "duplicate elements:\n",
    "\n",
    "```python\n",
    "def has_duplicates(t):\n",
    "    for i in range(0, len(t)):\n",
    "        elem_i = t[i]\n",
    "        for j in range(i + 1, len(t)):\n",
    "            elem_j = t[j]\n",
    "            if elem_i == elem_j:\n",
    "                return True\n",
    "    return False\n",
    "```\n",
    "\n",
    "Note that the number of times that the loop body of the inner loop runs in the worst case is equal to:\n",
    "\n",
    "$$(n-1) + (n-2) + ... + 1 + 0 = \\sum_{i=0}^{n-1} = \\frac{n(n-1)}{2}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 9** Derive the timing function for the following Python function that tests if a list contains any\n",
    "duplicate elements:\n",
    "\n",
    "```python\n",
    "def has_duplicates(t):\n",
    "    for i in range(0, len(t)):             1 * 1\n",
    "        elem_i = t[i]                      2 * n (1 list access, 1 assignment run n times)\n",
    "        for j in range(i + 1, len(t)):     1 * n\n",
    "            elem_j = t[j]                  2 * n(n-1)/2\n",
    "            if elem_i == elem_j:           2 * n(n-1)/2\n",
    "                return True                1 * 1\n",
    "    return False                           1 * 1\n",
    "```\n",
    "$f(n) = 4n(n-1)/2 + 3n + 3 = 2n^2 + n + 3$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Big-O notation\n",
    "\n",
    "Counting the exact number of elementary operations to estimate the time needed to run an algorithm can be useful\n",
    "in some circumstances, but you cannot immediately conclude that an algorithm requiring $2n + 2$ elementary\n",
    "operations is faster than a function requiring $3n + 5$ operations because different elementary operations take\n",
    "different amounts of time to perform on a real computer.\n",
    "\n",
    "Instead of trying to estimate the absolute amount of time required by a function, we can study how the number\n",
    "of operations scale as the size of the input scales. For example, what is the total number of elementary\n",
    "operations if the size of the input increases by a factor of 2?\n",
    "\n",
    "Big-O notation classifies algorithms into different complexity classes that describe how the time complexity\n",
    "scales as the size $n$ of the input scales for large values of $n$.\n",
    "\n",
    "The formal definition of Big-O notation is: For a given function $g(n)$ we say that $f(n)$ is in $O(g(n))$ if there are positive constants $c$ and $n_0$ such that\n",
    "\n",
    "$$\n",
    "| f(n) | \\leq c | g(n) | \\ \\text{for all} \\ n \\geq n_0\n",
    "$$\n",
    "\n",
    "In the analysis of algorithms, $f(n)$ is a timing function (that should not take on negative values) and $g(n)$ is positive for positive values of $n$. With these assumptions in mind, some authors say that $f(n)$ is an element of $O(g(n))$ if there are positive constants $c$ and $n_0$ such that\n",
    "\n",
    "$$\n",
    "0 \\leq f(n) \\leq c g(n)  \\ \\text{for all} \\ n \\geq n_0\n",
    "$$\n",
    "\n",
    "In CISC121 we are not very interested in the formal definition of big-O, and instead aim for a less formal\n",
    "understanding of big-O. To begin, let's consider the big-O complexity of the examples from the previous section:\n",
    "\n",
    "| timing function $f(n)$ | big-O complexity class |\n",
    "| :- | :- |\n",
    "| 7 | O$(1)$ |\n",
    "| $3n + 2$ | O$(n)$ |\n",
    "| $5n - 1$ | O$(n)$ |\n",
    "| $3n^2 + 4n + 3$ | O$(n^2)$ |\n",
    "\n",
    "From the table above, we see that $f(n) = 7$ is in O$(1)$.\n",
    "O$(1)$ is the *constant time* complexity class. Algorithms in this class require time that is independent of\n",
    "the size of the input $n$. Doubling the input size results in no change in the amount of time required. \n",
    "\n",
    "From the table above, we see that $f(n) = 3n+2$ and $f(n) = 5n-1$ are in O$(n)$.\n",
    "O$(n)$ is the *linear time* complexity class. Algorithms in this class require time that is directly\n",
    "proportional to the size of the input $n$. Doubling the input size results in doubling the amount of time required. \n",
    "\n",
    "From the table above, we see that $f(n) = 3n^2 + 4n + 3$ is in O$(n^2)$.\n",
    "O$(n^2)$ is the *quadratic time* complexity class. Algorithms in this class require time that is \n",
    "proportional to the square of the size of the input $n$. Doubling the input size results in\n",
    "quadrupling the amount of time required. \n",
    "\n",
    "Some other common $O$-notation classes are shown in the table below sorted in increasing complexity order:\n",
    "\n",
    "| Dominant term | Big-$O$ class | Description | Example algorithm |\n",
    "| :- | :- | :- | :- |\n",
    "| $c$ | O$(1)$ | constant time | array access |\n",
    "| $c \\log n$ | O$(\\log n)$ | logarithmic time | binary search of sorted array |\n",
    "| $c n$ | O$(n)$ | linear time | linear search of an unsorted array |\n",
    "| $c n \\log n$ | O$(n \\log n)$ | linearithmic time | fastest comparison-based sort |\n",
    "| $c n^2$ | O$(n^2)$ | quadratic time | selection sort, matrix-vector multiplication |\n",
    "| $c n^3$ | O$(n^3)$ | cubic time | naive matrix multiplication |\n",
    "| $c k^n$ | O$(k^n)$ | exponential time | exhaustive search of $n$ digit combination lock |\n",
    "| $c n!$ | O$(n!)$ | factorial time | Bogosort |\n",
    "\n",
    "In the *Dominant term* column, the $c$ can be any constant value. The dominant term of a timing function is\n",
    "the term in the function that grows most quickly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Going from $f(n)$ to O$(n)$\n",
    "\n",
    "In typical usage big-O notation applies to very large $n$. As $n$ approaches infinity, the contribution of the\n",
    "terms that grow \"most quickly\" in the timing function will cause the slower growing terms to become\n",
    "insignificant. This allows us to apply the following rules to remove terms from the timing function to obtain\n",
    "the big-O complexity class:\n",
    "\n",
    "1. If $f(n)$ is a single term then keep that term, and\n",
    "    1. If $f(n)$ is a constant then $f(n)$ is in O$(1)$\n",
    "    2. Otherwise, apply Rule 3 below\n",
    "2. If $f(n)$ is a sum of several terms, keep only the term that grows the fastest.\n",
    "    * It's useful to remember the following ordering of growth rates: \n",
    "    $$c < \\log(n) < \\sqrt{n} < n < n\\log(n) < n^2 < n^3 < 2^n < n!$$\n",
    "    where $c$ is any constant value\n",
    "3. If $f(n)$ is a product of several factors, any constants can be omitted.\n",
    "\n",
    "For $f(n) = 7$ we apply Rule 1, followed by Rule 1.1 to get O$(1)$.\n",
    "\n",
    "For $f(n) = 3n + 2$ we apply Rule 2 to get $3n$. We then apply Rule 3 to remove the constant $3$ to get\n",
    "O$(n)$.\n",
    "\n",
    "For $f(n) = 5n - 1$ we apply Rule 2 to get $5n$. We then apply Rule 3 to remove the constant $5$ to get\n",
    "O$(n)$.\n",
    "\n",
    "For $f(n) = 3n^2 + 4n + 3$ we apply Rule 2 to get $3n^2$. We then apply Rule 3 to remove the constant $3$ to get\n",
    "O$(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise 10** What is the big-O complexity class for each of the following functions:\n",
    "\n",
    "- $f(n) = 4n^3 + 1000n^2 - 32n + 5$\n",
    "- $f(n) = 24\\sqrt{n} + n + 1$\n",
    "- $f(n) = \\frac{\\sqrt{n}}{n} + n + 1$\n",
    "- $f(n) = n \\log(n) + n + n^2$\n",
    "- $f(n) = \\sum_{i=1}^{n} (1 + 2n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution: Exercise 10** What is the big-O complexity class for each of the following functions:\n",
    "\n",
    "- $O(n) = n^3$\n",
    "- $O(n) = n$ because $n$ grows faster than $\\sqrt{n}$\n",
    "- $O(n) = n$\n",
    "- $O(n) = n^2$\n",
    "- $f(n) = \\sum_{i=1}^{n} (1 + 2n) = \\sum_{i=1}^{n} 1 + \\sum_{i=1}^{n} 2n = n + 2n^2$, therefore $O(n) = n^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Estimating complexity when a function calls another function\n",
    "\n",
    "Because big-O analysis discards constant values, we can estimate the complexity of a function that calls\n",
    "a second function if we know the big-O complexity of the second function. Consider the function from\n",
    "Exercise 8:\n",
    "\n",
    "```python\n",
    "def union(s, t):\n",
    "    u = s[:]\n",
    "    for elem_t in t:\n",
    "        include = True\n",
    "        for elem_s in s:\n",
    "            if elem_s == elem_t:\n",
    "                include = False\n",
    "                break\n",
    "        if include:\n",
    "            u.append(elem_t)\n",
    "    return u\n",
    "```\n",
    "\n",
    "The inner loop is testing if `s` contains the element `elem_t`. We can replace the inner loop with the Python\n",
    "`in` operator:\n",
    "\n",
    "```python\n",
    "def union(s, t):\n",
    "    u = s[:]\n",
    "    for elem_t in t:\n",
    "        if elem_t not in s:\n",
    "            u.append(elem_t)\n",
    "    return u\n",
    "```\n",
    "\n",
    "When we count the number of elementary operations on each line, we use the big-O complexity of `in` for the\n",
    "number of elementary operations. `in` compares `elem_t` to every element in `s` in the worst case; thus, its\n",
    "big-O complexity is O$(n)$:\n",
    "\n",
    "```python\n",
    "def union(s, t):                    NUMBER OF OPERATIONS\n",
    "    u = s[:]                        n (makes a copy of the n elements of s)\n",
    "    for elem_t in t:                1\n",
    "        if elem_t not in s:         2 + O(n) (1 if, 1 not, 1 in)\n",
    "            u.append(elem_t)        1\n",
    "    return u                        1\n",
    "```\n",
    "\n",
    "For the purposes of counting operations, we replace O$(n)$ with $n$ because we know that big-O analysis will\n",
    "discard all constant factors.\n",
    "\n",
    "```python\n",
    "def union(s, t):                    NUMBER OF OPERATIONS\n",
    "    u = s[:]                        n (makes a copy of the n elements of s)\n",
    "    for elem_t in t:                1\n",
    "        if elem_t not in s:         2 + n\n",
    "            u.append(elem_t)        1\n",
    "    return u                        1\n",
    "```\n",
    "\n",
    "The lines of the loop body run at most $n$ times (once for each element in `t`) and all other lines run once;\n",
    "thus, the timing function for `union` is:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "f(n) & = n + 1 + n(2 + n) + n + 1 \\\\\n",
    "& = n^2 + 4n + 2\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## So what does all of this mean?\n",
    "\n",
    "Big-O notation allows us to compare how the time required by different algorithms scale with the input size.\n",
    "If you have two algorithms in the same complexity class, then the time required by both algorithms scale\n",
    "in the same way as the input size increases (for large input sizes). If you have two algorithms in different\n",
    "complexity classes, then the time required by both algorithms scale differently as the input size increases\n",
    "(for large input sizes).\n",
    "\n",
    "As a rule of thumb, when you have a choice between different algorithms that perform the same task, you should\n",
    "prefer the algorithm with the lesser complexity class keeping in mind that:\n",
    "\n",
    "* big-O analysis only applies to large input sizes\n",
    "    * For small input sizes an algorithm having greater big-O complexity may be faster in practice. Python's\n",
    "    standard sorting algorithm uses a O$(n^2)$ algorithm for short lists and a O$(n\\log(n))$ algorithm for\n",
    "    longer lists.\n",
    "* the worst-case complexity may never occur in practice\n",
    "    * It is possible to perform a big-O analysis for the average-case and best-case complexities. An algorithm\n",
    "    with a poor worst-case complexity may have a better average-case complexity.\n",
    "* other factors may be equally important or more important than computational complexity\n",
    "    * Algorithms with better big-O computational complexity sometimes have worse big-O memory complexity. If\n",
    "    memory is an important resource in your application, then you might prefer an algorithm with worse big-O\n",
    "    computational complexity.\n",
    "    \n",
    "If two algorithms have the same computational complexity, then the big-O complexity does not help in deciding\n",
    "which algorithm to choose. In these situations, you have to rely on experimentation to determine which algorithm\n",
    "to use if computational speed is a high priority."
   ]
  },
  {
   "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.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}