{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8482c897",
   "metadata": {},
   "source": [
    "# Complexity\n",
    "\n",
    "Complexity analysis estimates how runtime and memory grow as input size increases.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8325a81a",
   "metadata": {},
   "source": [
    "## Why complexity matters\n",
    "\n",
    "Measured runtime depends on machine and environment. Complexity gives machine-independent\n",
    "growth behavior."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fdeb5c5",
   "metadata": {},
   "source": [
    "## Big-O quick reference\n",
    "\n",
    "- `O(1)`: constant work\n",
    "- `O(n)`: linear work\n",
    "- `O(n log n)`: typical efficient sorting\n",
    "- `O(n^2)`: nested loops over same data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1d2a3e5",
   "metadata": {},
   "source": [
    "## Common patterns\n",
    "\n",
    "Single pass:\n",
    "\n",
    "```csharp\n",
    "for (int i = 0; i < n; i++) { ... } // O(n)\n",
    "```\n",
    "\n",
    "Nested pass:\n",
    "\n",
    "```csharp\n",
    "for (int i = 0; i < n; i++)\n",
    "    for (int j = 0; j < n; j++) { ... } // O(n^2)\n",
    "```\n",
    "\n",
    "Halving loop:\n",
    "\n",
    "```csharp\n",
    "while (n > 1) n /= 2; // O(log n)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9a771a5",
   "metadata": {},
   "source": [
    "## Space complexity\n",
    "\n",
    "Track extra memory, not input storage:\n",
    "\n",
    "- fixed temporaries: `O(1)`\n",
    "- additional array of size `n`: `O(n)`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3faae0b",
   "metadata": {},
   "source": [
    "## Practical use\n",
    "\n",
    "Use complexity to choose algorithms first, then benchmark with realistic data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "footnotes",
   "metadata": {},
   "source": [
    "```{rubric} Footnotes\n",
    "```\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "csharp"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}