big_o.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Time complexity and Big O notation\n",
    "\n",
    "_Author: Mahdi Shadkam-Farrokhi_  \n",
    "[Website](https://mahdis.pw/) | [LinkedIn](https://www.linkedin.com/in/mahdi-shadkam-farrokhi/) | [GitHub](https://github.com/Shaddyjr)\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "1. [Lesson Objectives](#Lesson-Objectives)\n",
    "1. [Lesson](#Lesson)\n",
    "1. [Exercises](#Exercises)\n",
    "1. [Recap](#Recap)\n",
    "1. [Resources](#Resources)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lesson Objectives\n",
    "- Students will be able to assess an algorithm's time complexity using big O notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lesson"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why bother with time complexity? Hardware limitations!\n",
    "\n",
    "Many many moons ago, [vacuum tubes](https://en.wikipedia.org/wiki/Vacuum_tube) were used in early computers as a switch or an amplifier and were notoriously bulky.\n",
    "<img src=\"assets/tubes.jpg\" width=\"400px\">\n",
    "There was only so many tubes that could reasonably fit within a space, and, in fact, many of the earliest computers were unwieldy and took up entire rooms. Processing speeds were also prohibative. With modern advances in technology, some simple calculators now have more computing power than many of these primative computers.\n",
    "\n",
    "Our modern computers are VERY powerful, but are still __limited by two fundamental hardware resources - space and processing speed__.\n",
    "\n",
    "---\n",
    "As such, programmers, developers, and engineers need to consider how much _space and time_ the work they're doing will require. I can give you a dataset with 10 thousand observations and you could load it into memory, do data cleaning, EDA, etc. But if I gave you 60 terabytes of data, your laptop wouldn't be able to load even 1% of that data, let alone conduct operations on it. \n",
    "\n",
    "Tech companies have systems in place that CAN handle terabytes of LIVE streaming data. How can they do this? They ensure employees have a strong fundamental understanding of __space and time complexity__ when creating _algorithms._\n",
    "\n",
    "_NOTE: for this lesson, we'll only refer to time complexity, but the same foundational understanding will apply._\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What's an algorithm?\n",
    "An algorithm is __a set of instructions that produce a desired output or effect__. We use these every day, and I'm not just talking about with computers!\n",
    "\n",
    "It can often be challenging to create a well made algorithm for even a seemingly simple task - [source](https://www.youtube.com/watch?v=cDA3_5982h8):\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The problem with algorithm runtimes\n",
    "You have 3 computers: an old laptop, a new laptop, and a super computer.\n",
    "\n",
    "Each computer runs __the same code,__ and here is the runtime for each computer:\n",
    "- old laptop: 3 minutes\n",
    "- new laptop: 30 seconds\n",
    "- super computer: 2 nanoseconds\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary>\n",
    "        <strong>What is the algorithm's runtime?</strong>\n",
    "    </summary>\n",
    "        <p>We don't know! Every computer is different (even running the same code on the same computer can result in different runtimes!).</p>\n",
    "    <p>Using the literal amount of time an algorithm takes to run on any one computer does not properly convey the truth - <strong>we need another way to objectively describe the algorithm's runtime that is independent of the computer it's run on.</strong></p>\n",
    "</details>\n",
    "\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary>\n",
    "        <strong>If we double the workload on the algorithm, what happens to the runtime?</strong>\n",
    "    </summary>\n",
    "        <p>We don't know! We have no basis for comparison.</p>\n",
    "        <p>Running the algorithm once won't tell us about how much the runtime will increase with increasing input.</p>\n",
    "        <p>We COULD run the algorithm MANY times (Monte Carlo style) to construct a graph of how the runtime increases with more input, but this is VERY impractical - <strong>we need another way to quickly describe how the runtime changes with the size of the input</strong></p>\n",
    "</details>\n",
    "\n",
    "---\n",
    "Big O notation is the solution to both of these problems!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.random.seed(777)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Motivating Example\n",
    "- Bob has a deck of 10 cards, each with a number on it.  \n",
    "- Bob wants to find the largest number out of the 10.\n",
    "- __Algorithm:__ To do this, he'll look at each card in the deck, keeping the largest number he's seen thus far until there are no more cards left.\n",
    "\n",
    "<br/>\n",
    "\n",
    "<details>\n",
    "    <summary>\n",
    "        Can Bob only look at half of the cards?\n",
    "    </summary>\n",
    "            No, he must look at all of the cards, otherwise he might miss the true largest number.\n",
    "</details>\n",
    "\n",
    "<br/>\n",
    "<details>\n",
    "    <summary>\n",
    "        If Bob had 1000 cards, would it take him the same amount of time to find the largest number?\n",
    "    </summary>\n",
    "    Certainly not! The more elements you need to consider, the longer the <i>algorithm</i> will take.\n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "# we might represent this situation in code as...\n",
    "cards = [4, 5, 7, 1, 47, 6, -2, 78, 0, 42]\n",
    "largest_thus_far = -float('inf') # negative inifity is smallest possible number\n",
    "\n",
    "for card in cards:\n",
    "    if card > largest_thus_far:\n",
    "        largest_thus_far = card\n",
    "\n",
    "largest_thus_far"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is Time Complexity?\n",
    "- Time complexity measures how much work an algorithm has to do, when the number of elements $n$ increases.\n",
    "- Time complexity ignores machine specific differences and objectively looks at __the rate of growth of an algorithm's runtime ($N$) based on the number of elements ($n$)__\n",
    "\n",
    "\n",
    "In the example with Bob:\n",
    "- Bob checks every card/element once.\n",
    "- As $n$, the number of cards increases, the time it takes Bob to finish ($N$) also increases, at a 1:1 rate (linear).\n",
    "\n",
    "__So, why is this relevant?__  \n",
    "We've (mostly) only using a relatively small amount of data, which makes time complexity largely irrelevant (as you can see in the graph below). However, when working with larger data sets, the time complexity of an algorithm can have a HUGE impact! \n",
    "\n",
    "<img src=\"assets/complexity_graph.png\" width=\"400px\">\n",
    "\n",
    "__The more efficienty your code, the less time it takes to complete tasks!__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What is Big O notation?\n",
    "- Big O notation is how time complexity is represented, and written in the form $O(\\text{complexity})$, where $\\text{complexity}$ is the total number of elements the algorithm must consider - usually in terms of $n$.\n",
    "\n",
    "<img src=\"assets/big-o-complexity-graph.jpg\" width=\"500px\">\n",
    "\n",
    "<br/>\n",
    "\n",
    "\n",
    "- __Big O notation, unless otherwise states, ALWAYS considers the WORST possible scenario for the algorithm.__\n",
    "\n",
    "Consider the practical application in the real world, where computers will house the data and execute operations on that data. If we don't account for the worst scenario, we could end up running into errors, [buffer overflows](https://en.wikipedia.org/wiki/Buffer_overflow), or worse - [data corruption](https://en.wikipedia.org/wiki/Data_corruption).\n",
    "\n",
    "For example, you have a list of $n$ length and you want to find the first number that's greater than 0. \n",
    "- Yes, you MIGHT find the number immediately and can stop searching, $O(1)$...but that's a very naive assumption. \n",
    "- The WORSE possible situation for our algorithm is to assume the first number greater than 0 is the LAST number, meaning we must check EVERY value $O(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Constant Time: O(1)\n",
    "\n",
    "The simplest example of time complexity is constant time complexity $O(1)$. Even if the number of elements increases, operations that take constant time always take the same amount of time.\n",
    "\n",
    "__This is the quickest possible run time!__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1 thousand random integers\n",
    "one_thousand_nums = np.random.randint(1_000_000, size = 1000)\n",
    "\n",
    "# 1 million random integers\n",
    "one_mil_nums = np.random.randint(1_000_000, size = 1_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "one_thousand_nums[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, let's get the last element of a list. This is easily done in python by using the `-1` index.\n",
    "\n",
    "__Does this operation of selecting the last element take longer if the list is longer?__  \n",
    "Let's find out!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "one_thousand_nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "one_mil_nums[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Taking the last element in a list takes the same amount of time regardless of how large the list is - it's an operation that takes $O(1)$, or constant time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterating over a single collection of elements using one loop (Linear time): $O(n)$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "cards = one_thousand_nums\n",
    "largest_thus_far = -float('inf') # negative inifity is smallest possible number\n",
    "\n",
    "for card in cards:\n",
    "    if card > largest_thus_far:\n",
    "        largest_thus_far = card\n",
    "\n",
    "largest_thus_far"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "cards = one_mil_nums # Using 1 million now\n",
    "largest_thus_far = -float('inf') # negative inifity is smallest possible number\n",
    "\n",
    "for card in cards:\n",
    "    if card > largest_thus_far:\n",
    "        largest_thus_far = card\n",
    "\n",
    "largest_thus_far"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_NOTE: I'm using the `%%time` simply to show the algorithm is affected by the size of the input list. Do NOT read too much into the literal amount of time your code took to run versus anyone elses. Everyone's machine is different and even the same machine will have spikes in processing speed that results in different run times._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### An Aside: Abstraction into functions\n",
    "\n",
    "With so much repeated code, your programmer knee-jerk reaction should start kicking it! We should consider creating a function to help abstract this repeated code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_largest(cards): # cards are now parameter\n",
    "    largest_thus_far = -float('inf')\n",
    "\n",
    "    for card in cards:\n",
    "        if card > largest_thus_far:\n",
    "            largest_thus_far = card\n",
    "\n",
    "    return largest_thus_far # added return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "find_largest(one_thousand_nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "find_largest(one_mil_nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterating over half of the collection: $O(\\frac{n}{2}) = O(n)$\n",
    "\n",
    "Remember, time complexity is about the __rate of growth in runtime__. So, dividing by a constant (like 2) may change the literal number of elements to consider, but __the overall rate is still determined by $n$__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### An Aside: The dominant term dominates\n",
    "\n",
    "Since the runtime is dominated by the most complex term, all other terms can effectively be ignored.\n",
    "\n",
    "For example, an algorithm has the following total complexity: \n",
    "$$O(n^2 + n + 5)$$\n",
    "\n",
    "__As the number of elements $n$ gets VERY large, does the 5 really matter? What about the $n$?__  \n",
    "__The $n^2$ will completely overshadow the other terms to insignificance.__\n",
    "\n",
    "Therefore, we can say:\n",
    "$$O(n^2 + n + 5) = O(n^2)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterating over two separate collections using two different loops: $O(n+m)$\n",
    "\n",
    "You will sometimes see other variables in Big O notation. These other variables (like $m$ or $k$) are referring to other inputs to the algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# given 2 lists, return sum of both\n",
    "def sum_two_lists(list_1, list_2):\n",
    "    total = 0\n",
    "    for num in list_1:\n",
    "        total += num\n",
    "    \n",
    "    for num in list_2:\n",
    "        total += num\n",
    "    \n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice:\n",
    "- How the above algorithm treats each list separately - meaning the entire runtime is determined by the time it takes for the first list to loop, followed by the second. \n",
    "- Each statement (`for` loop) in the algorithm is treated separately and then combined in the appropriate way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# establish some lists\n",
    "odds      = list(range(1,1_000_000, 2)) # list of first 1 million odd numbers\n",
    "fibonacci = [1, 1, 2, 3, 5, 8, 13, 21]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "sum_two_lists(odds, fibonacci)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### An Aside: Default Python functions\n",
    "\n",
    "You might be thinking these are toy examples - we could simply use `sum()` to solve the above problem.\n",
    "\n",
    "Using `sum()` is convenient, but that's it!\n",
    "\n",
    "__What do you think `sum()` is doing?__  \n",
    "The developers who created the `sum()` function and set it as a default STILL have to access all $n$ elements to calculate the sum.\n",
    "\n",
    "_NOTE: Clever developers get bonus efficiency by implementing the algorithm in a lower-level language (Cython)_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# same example using `sum()`\n",
    "def sum_two_lists_with_default_sum(list_1, list_2):\n",
    "    total = 0\n",
    "    total += sum(list_1)\n",
    "    total += sum(list_2)\n",
    "    \n",
    "    return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "sum_two_lists_with_default_sum(odds,fibonacci)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterating over a single collection using two nested loops (Quadratic time): $O(n^2)$.\n",
    "\n",
    "We're thinking of rebranding our company's name and we have brainstormed a list of cool words we want to include in the name.\n",
    "\n",
    "The leadership team has decided to use a two word name, but can't decide which combination of words works best. So...let's see all of the combinations! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_combinations(the_list):\n",
    "    results = []\n",
    "    for item in the_list:\n",
    "        for inner_item in the_list:\n",
    "            results.append(f\"{item} {inner_item}\")\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice:\n",
    "- How the above algorithm treats each list separately - this time, however, the inner loop is nested within the outer loop leading to $O(n \\cdot n) = O(n^2)$ \n",
    "- Each statement (`for` loop) in the algorithm is treated separately and then combined in the appropriate way"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cool_words = [\n",
    "    \"Big\",\n",
    "    \"Data\",\n",
    "    \"Analytics\",\n",
    "    \"Artificial\",\n",
    "    \"Intelligence\",\n",
    "    \"Machine\",\n",
    "    \"Personalization\",\n",
    "    \"Recognition\",\n",
    "    \"Augmented\",\n",
    "    \"Virtual\",\n",
    "    \"Robotics\",\n",
    "    \"Smart\",\n",
    "    \"Internet\",\n",
    "    \"Quantum\",\n",
    "    \"Blockchain\",\n",
    "    \"Technological\"\n",
    "]\n",
    "\n",
    "all_combinations(cool_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### An aside: Ignoring insignificant components\n",
    "\n",
    "We've been glossing over something that seem minor, but is worth discussing.\n",
    "\n",
    "Each part of the algorithm must be evaluated by the computer and therefore contributes to the runtime. Let's look at our last example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_combinations(the_list):\n",
    "    results = []\n",
    "    for item in the_list:\n",
    "        for inner_item in the_list:\n",
    "            results.append(f\"{item} {inner_item}\")\n",
    "    return results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Combining all of the parts, we see why we're quick to ignore the insignificant components. \n",
    "\n",
    "$$O(1) + O(n) \\cdot (O(n) + O(1)) + O(1)$$\n",
    "\n",
    "As we saw earlier, those constant values will pale in comparison to the most significant component and are ignore.\n",
    "\n",
    "$$O(1) + O(n) \\cdot (O(n) + O(1)) + O(1) = O(n\\cdot n) = O(n^2)$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterating over two different collections using two nested loops: $O(n\\cdot m)$\n",
    "\n",
    "We're given two lists, where the first list is a set of unique names (strings) of people we're looking for and the second list is a roster of all students in a school, potentially with repeated names.\n",
    "\n",
    "We want to find all students with the names from the first list.\n",
    "\n",
    "For example:\n",
    "\n",
    "```python\n",
    "find_names = [\"amy\",\"bob\"]\n",
    "students = [\"amy graham\",\"bob summers\",\"charlie rose\",\"dan the man\",\"emily smalls\",\"amy rose\"]\n",
    "\n",
    "find_students(find_names, students) # ['amy graham', 'amy rose', 'bob summers']\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_students(names, students):\n",
    "    output = []\n",
    "    \n",
    "    for name in names:\n",
    "        for student in students:\n",
    "            if name in student:\n",
    "                output.append(student)\n",
    "    \n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_names = [\"amy\",\"bob\"]\n",
    "students = [\"amy graham\",\"bob summers\",\"charlie rose\",\"dan the man\",\"emily smalls\",\"amy rose\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "find_students(find_names, students)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sorting a collection: $O(nlog(n))$\n",
    "\n",
    "Sorting algorithms are an entire group of problems on it's own and is beyond the scope of this lesson. Check out the [Resources](#Resources) to learn more.\n",
    "\n",
    "It will suffice to say, given most situations, if you need a sorting algorithm you can find one that runs in $O(nlog(n))$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lookup time: $O(1)$\n",
    "\n",
    "Indexing a list or using a key on a dictionary is known as a \"lookup\". This refers to __looking up to see if the index or key exists__ and returning the associated value. For all extensive purposes, lookup is effevtively constant time.\n",
    "\n",
    "Check out other [common Python operation time complexities](https://wiki.python.org/moin/TimeComplexity), such as `.pop()` or `.append()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# creating large list\n",
    "large_num_list = list(range(1_000_000))\n",
    "# creating large dictionary\n",
    "large_hash_map = {f\"key_{num}\":num for num in range(1_000_000)}\n",
    "# creating large set\n",
    "large_set = set(range(1_000_000))\n",
    "\n",
    "print(f\"large_num_list has {len(large_num_list)} elements\")\n",
    "print(f\"large_hash_map has {len(large_hash_map)} elements\")\n",
    "print(f\"large_set has {len(large_set)} elements\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%time\n",
    "# lookup for list\n",
    "large_num_list[100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%time\n",
    "# lookup for dictionary\n",
    "large_hash_map[\"key_100\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%time\n",
    "# lookup for dictionary using .get\n",
    "large_hash_map.get(\"key_100\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_NOTE: Using `.get()` ensures no errors if key doesn't exist_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%time\n",
    "# lookup for set using \"in\"\n",
    "100 in large_set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__NOTE: You're computer is optimized to do math! Consider math operations as being constant time, $O(1)$, too!__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimizing runtime\n",
    "\n",
    "There are many paths to get same result, but some can be more efficient than others.\n",
    "\n",
    "__On coding interviews you may very well encounter a coding challenge where you may be asked to consider a \"brute force\", or inefficient solution, and then improve on it by finding a more optimal solution.__\n",
    "\n",
    "Recognize how significant it is to take a $O(n^2)$ problem and reduce it's time complexity to $O(n)$\n",
    "\n",
    "__Even if you aren't able to get to the most optimal solution, the mere fact you CONSIDER runtime and use Big O notation conveys to employers that you're aware of the importance of efficient code!__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "State the runtime using Big O notation to the following exercises:\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1) Consecutive Sum\n",
    "\n",
    "Give a list of numbers, return a new list of the consecutive, or running, sum.\n",
    "\n",
    "```python\n",
    "nums = [4,5,67,7,1,5,78,1]\n",
    "consec_sum(nums) # [4, 9, 76, 83, 84, 89, 167, 168]\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# METHOD 1: standard for loop and running counter\n",
    "def consec_sum(numbers):\n",
    "    output = []\n",
    "    running_total = 0\n",
    "    \n",
    "    for number in numbers:\n",
    "        running_total +=  number\n",
    "        output.append(running_total)\n",
    "    \n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Answer:__ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### TESTING ###\n",
    "nums = [4,5,67,7,1,5,78,1]\n",
    "consec_sum(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__MINI BONUS!__ Refactor the code to do this operation in place, meaning the original list is altered. Instead of returning a new list return the SAME list (now altered). Consider how this affects the space the algorithm needs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# METHOD 2: space efficient by reusing input list (WARNING: this alters the input list!)\n",
    "def consec_sum(numbers):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "### TESTING ###\n",
    "nums = [4,5,67,7,1,5,78,1]\n",
    "consec_sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check on the original list, which should be changed!\n",
    "nums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Find average length word\n",
    "\n",
    "Given a list of words, find the one word with the average length (assume there will always be one word with the average length).\n",
    "\n",
    "```python\n",
    "words = [\"one\",\"money\",\"i\"]\n",
    "avg_len_word(words) # 'one'\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def avg_len_word(words):\n",
    "    # First get total length of words\n",
    "    total_of_word_lengths = 0\n",
    "    for word in words:\n",
    "        total_of_word_lengths += len(word)\n",
    "        \n",
    "    avg_len = total_of_word_lengths / len(words) # get average length\n",
    "    \n",
    "    # loop through list to get average length word (gauranteed to be one)\n",
    "    for word in words:\n",
    "        if len(word) == avg_len:\n",
    "            return word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Answer:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### TESTING ###\n",
    "words = [\"one\",\"money\",\"i\"]\n",
    "avg_len_word(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) $a^3 + b^3 = c^3 + d^3$\n",
    "\n",
    "All values $a,b,c,d$ are integers between 1-50. Find all solutions to $a^3 + b^3 = c^3 + d^3$\n",
    "\n",
    "_NOTE: $a,b,c,d$ must be unique from each other_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_cubed_values(n):\n",
    "    solutions = []\n",
    "    for a in range(1,n+1):\n",
    "        for b in range(1,n+1):\n",
    "            for c in range(1,n+1):\n",
    "                for d in range(1,n+1):\n",
    "                    all_four_values = [a,b,c,d]\n",
    "                    all_unique_values = set(all_four_values)\n",
    "                    if len(all_unique_values) == 4 and a**3 + b**3 == c**3 + d**3:\n",
    "                        all_four_values.sort()\n",
    "                        if all_four_values not in solutions:\n",
    "                            solutions.append(all_four_values)\n",
    "    return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solutions = get_cubed_values(n = 50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Answer:__\n",
    "\n",
    "_NOTE: With some modifications to this algorithm, we can reduce the time complexity down to $O(n^2)$ - [source](https://stackoverflow.com/questions/14454133/find-all-the-quadruples-a-b-c-d-where-a3-b3-c3-d3-when-1-a-b/20901679#20901679)_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check out solutions\n",
    "solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge A\n",
    "__Given a list of numbers, return `True` if the list contains duplicates and `False` otherwise.__\n",
    "\n",
    "__Use either of the following tactics:__\n",
    "1. Two \"for\" loops (Brute Force)\n",
    "2. Sort the list and compare neighboring values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# METHOD #1: Brute Force\n",
    "def slow_duplicate_solution(nums):\n",
    "    # loop through each number\n",
    "        # loop again through each number\n",
    "            # skipping self, if duplicate found, stop and return True\n",
    "    \n",
    "    # got through entire list without finding duplicate, return False\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# METHOD #2: Sorting\n",
    "def slow_duplicate_solution(nums):\n",
    "    # sort input list (technically, this modifies the input list)\n",
    "    # loop through sorted list\n",
    "        # if previous neighbor num is same as current num, return True  \n",
    "\n",
    "    # got through entire list without finding duplicate, return False\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### TESTING ###\n",
    "dups = [1,4,5,7,2,4,6,0]\n",
    "print(slow_duplicate_solution(dups)) # True\n",
    "\n",
    "uniques = [4,5,6,7,9,2,3,10,89]\n",
    "print(slow_duplicate_solution(uniques)) # False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__What's the time complexity for this solution?__\n",
    "\n",
    "_Answer:_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge B\n",
    "\n",
    "__Given a list of numbers, return `True` if the list contains duplicates and `False` otherwise.__\n",
    "\n",
    "__Complete the task in $O(n)$ time complexity__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def efficient_duplicates(nums):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### TESTING ###\n",
    "dups = [1,4,5,7,2,4,6,0]\n",
    "print(efficient_duplicates(dups)) # True\n",
    "\n",
    "uniques = [4,5,6,7,9,2,3,10,89]\n",
    "print(efficient_duplicates(uniques)) # False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For an even _more optimized solution_, watch Joma Tech solve a similar problem in $O(n)$ time complexity and $O(1)$ space complexity:\n",
    "1. [If Programming Was An Anime](https://www.youtube.com/watch?v=pKO9UjSeLew)\n",
    "2. [Floyd's Tortoise and Hare Solution Explained](https://www.youtube.com/watch?v=9YTjXqqJEFE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recap\n",
    "- You should be able to assess an algorithm's time complexity using big O notation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resources\n",
    "- [Big O Notation Cheat Sheet](https://medium.com/@salmaeng71/big-o-notation-cheat-sheet-4a7e5632c93e)\n",
    "- [Sorting Algorithm Visualization](https://www.toptal.com/developers/sorting-algorithms)\n",
    "- `Complexity_Cheatsheet.pdf` (within repo)\n",
    "- [Big O Time Complexity Simplified](https://www.thecodingdelight.com/big-o-time-complexity-simplified/)\n",
    "- [Big-O from a self-taught programmer's perspective](https://justin.abrah.ms/computer-science/big-o-notation-explained.html)\n",
    "- [Common Python operation time complexities](https://wiki.python.org/moin/TimeComplexity)"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}