activities/a01_complexity-big-O.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DSCI 512 Lecture 1 Activities\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## True/False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assume Algorithm A runs in $O(n)$ time and Algorithm B runs in $O\\left(\\sqrt{n}\\right)$ time.\n",
    "\n",
    "1. Running Algorithm A with $n=20000$ will probably take 2x as long as running it with $n=10000$.\n",
    "2. Running Algorithm A with $n=2$ will probably take 2x as long as running it with $n=1$.\n",
    "3. Running Algorithm B with $n=20000$ will probably take 4x as long as running it with $n=10000$.\n",
    "4. Without more information, there is no way of knowing which algorithm will be faster on a particular task.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:**\n",
    "\n",
    "1. True\n",
    "2. False\n",
    "3. False. That would be $O(n^2)$ behaviour, this is square root. So it should be $\\sqrt 2$ times longer.\n",
    "4. True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Old Quiz Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each of the following running times, indicate whether their asymptotic running time (i.e. the big O) is faster, the same as, or slower than linear time (i.e. $O(n)$). That is to say, if $n \\rightarrow \\infty$, would you expect the code to run faster/slower/same as $O(n)$ code.\n",
    "\n",
    "The first one is done for you as an example.\n",
    "\n",
    "**NOTE:** there is something confusing about the terminology. If the running time grows _faster_ as a function of $n$ that means the code runs _slower_ (because it takes more time to run). Hopefully the example below clarifies which one is being asked.\n",
    "\n",
    "|         Function &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  &nbsp; &nbsp; &nbsp;          | Faster, same, or slower?   |\n",
    "| --------------------------|--------|\n",
    "| $1$                         | _Faster_ |\n",
    "| $\\log n$                   | _Faster_ |\n",
    "| $2^{100}$                     | _Faster_ -- this is $O(1)$  |\n",
    "| $2^n$                       | _Slower_ |\n",
    "| $1000\\times n^{0.99}$        | _Faster_ -- $n^{0.99}$ vs. $n^1$ |\n",
    "| $n^2$                       | _Slower_ |\n",
    "| $4 \\log n + 16n$             | _Same_ |\n",
    "| $n \\log n$                   | _Slower_ |\n",
    "| $n/4$                       |  _Same_  |\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q2\n",
    "\n",
    "I ran a function `f` for different values of its input, `n`, and timed it. Here are the results:\n",
    "\n",
    "|   n  | time (sec) |\n",
    "|------|------|\n",
    "| 10  |  7.59  |\n",
    "| 100 | 25.2  |\n",
    "| 1000 |  75.8 |\n",
    "| 10000 | 251  | \n",
    "| 100000 | 759  |\n",
    "\n",
    "Given these results, what is the most plausible time complexity of `f`? \n",
    "\n",
    "Multiple choice options: \n",
    "\n",
    "- $O(1)$\n",
    "- $O(\\log n)$\n",
    "- $O(\\sqrt n)$\n",
    "- $O(n)$\n",
    "- $O(n \\log n)$\n",
    "- $O(n^2)$\n",
    "- $O(2^n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** $O(\\sqrt n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Q3\n",
    "\n",
    "Using big-O notation, for each code snippet below determine the time _and_ space complexity as a function of $n$. You can assume $n$ is always a positive integer. Also include a brief explanation and **list any assumptions you have made**.\n",
    "\n",
    "Note: the question is intended to be answered without running the code, but you can run it if you want to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(n):\n",
    "    x = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** Time $O(n)$, Space $O(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 10\n",
    "x = dict()\n",
    "\n",
    "for i in range(n):\n",
    "    x[i] = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** Time $O(n)$, Space $O(n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [],
   "source": [
    "x = np.ones((n,n))\n",
    "y = np.sum(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** Time $O(n^2)$, Space $O(n^2)$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lots_of_stuff(n):\n",
    "    x = []\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            if i == j:\n",
    "                x.append(\"Stuff\")\n",
    "            else:\n",
    "                y = 1 # a useless operation\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** Time $O(n^2)$, Space $O(n)$ because it only appends to the list $n$ times. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while n > 0:\n",
    "    n = n//2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** Time $O(\\log n)$, Space $O(1)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wondering about `//`? Documentation reproduced from [here](https://docs.python.org/3.8/glossary.html):\n",
    "> Mathematical division that rounds down to nearest integer. The floor division operator is `//`. For example, the expression `11 // 4` evaluates to `2` in contrast to the `2.75` returned by float true division. Note that `(-11) // 4 is -3` because that is `-2.75` rounded _downward_. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.6 ('dsci512')",
   "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.10.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "833530e805897aab5e7a30ee530b0bcb4cd19373b840f29eae5897b61b26002e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}