![](\"good-steps1.png\")
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How long it takes to execute that third might depend on whether a number is even or odd, but it's *bounded*. As the size of `input_nums` grows and grows, it won't keep getting slower and slower to execute that step once (that step will execute more times, but that's a separate point).\n", "\n", "If there are N=10 (where N is `len(input_nums)`), then a total of $1+11+10+1$ steps will execute total. In general, $f(N) = 2*N + 3$ gives the number of steps that will executed for a given input length.\n", "\n", "Here's an example of an illegitimate way to identify steps:\n", "\n", "
![](\"bad-steps.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Going back to the definition, that second box surrounds a snippet of code that keeps \"getting slower will growing input size.\" The execution time to *run that snippet once* is not bounded, so it's not a single step.\n",
"\n",
"Let's consider an anthor valid way to identify steps:\n",
"\n",
"![](\"good-steps2.png\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, the number of steps that execute depends on whether the numbers are odd or even. If all are odd, and $N=10$, there will be $1+11+10+10+1=33$ steps. If all are even, there will be $1+11+10+1=23$. Unless specified otherwise, we'll be doing *worst case analysis*, so we'll go with $f(N) = 3*N + 3$.\n",
"\n",
"Notice that this $f(N)$ is different than the function we got when we counted steps differently in the first example ($f(N) = 3*N + 3$), even though both approaches to counting steps were legitimate. Fortunately, it's all good, because both $f$ functions are in the $O(N)$ complexity class.\n",
"\n",
"Let's consider some more examples:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"nums = [1, 3, 4, 2, 5, 3, 6, 4]"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# example 1: O(N)\n",
"x = 3\n",
"x in nums"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above `x in nums` snippet in $O(N)$. Even though it's one line of code, that one line is not a single step, as Python essentially loops over all numbers looking for 3.\n",
"\n",
"In this case, Python will quickly find 3 at index 1 and stop, but for complexity analysis, we want to think about what happens in the worst case for different `nums` lists. The list might not even contain the number we're looking for, so Python might need to check every entry."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# example 2: O(1)\n",
"total = 0\n",
"for x in nums[:100]:\n",
" total += x\n",
"x"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It's not common to find loops in O(1) code, but in this case, the execution time is bounded. After `len(nums) > 100`, the code won't keep getting slower and slower as the list grows, because it only looks at the first 100."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"duplicate!\n",
"duplicate!\n",
"duplicate!\n",
"duplicate!\n"
]
}
],
"source": [
"# example 3: O(N**2)\n",
"for i in range(len(nums)):\n",
" for j in range(len(nums)):\n",
" if i != j and nums[i] == nums[j]:\n",
" print(\"duplicate!\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, we're looping over every pair of numbers in the list. If there are N numbers, there are N numbers, there are $N^2$ pairs."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"duplicate!\n",
"duplicate!\n"
]
}
],
"source": [
"# example 4: O(N**2)\n",
"\n",
"# part 1: filter to odd numbers\n",
"odds = []\n",
"for x in nums:\n",
" if x % 2 == 1:\n",
" odds.append(x)\n",
"\n",
"# part 2: are there any duplicates among our odd numbers?\n",
"for i in range(len(odds)):\n",
" for j in range(len(odds)):\n",
" if i != j and odds[i] == odds[j]:\n",
" print(\"duplicate!\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, we have two phases, the first of which is $O(N)$, and the second of which is $O(N^2)$. Together, it is $O(N + N^2)$, which is actually the same as $O(N^2)$ (a better answer since it is simpler). "
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.9.6"
}
},
"nbformat": 4,
"nbformat_minor": 2
}