I have been working though CSE 373 Lectures by Skiena and I cannot understand his explanation of why multiplication by a constant does not change the asymptotics:
$O(c*f(n)) \to O(f(n))$
In the lectures, Skiena gives the example with $c = 100$ and $f(n) = n^3$. Next, he proceeds with showing that there is a constant $C$ such that $100n^3 < C*n^3$.
Doesn't it just show that $g(n) = 100n^3$ is bounded by $C*n^3$? How does it tell us anything about the $O(c*f(n))$?
Doesn't it just show that $g(n)=100n^3$ is bounded by $C∗n^3$?
Well that is what it means to be $O(n^3)$ by definition. Recall that $g$ is $O(f)$ if there exists a positive constant $C$ and some $x_0$ such that $|g(x)|\leq C\cdot f(x)$ for all $x\geq x_0$. In other words, $g$ is $O(f)$ if it is eventually dominated by $C\cdot f$.
Hence a function is $O(n^3)$ if it is eventually dominated by $C\cdot n^3$, where $C$ is some fixed positive constant. In the example given $100n^3$ is in $O(n^3)$ because it is eventually dominated by e.g. $101\cdot n^3$.
In general, if $g\in O(c\cdot f)$, then for some fixed constant $C$ we eventually have $|g(x)|\leq C \cdot (c\cdot f(x)) = (C\cdot c)\cdot f(x)$. Now with $D=C\cdot c$ as the constant we eventually have $|g(x)|\leq D\cdot f(x)$, therefore $g$ is $O(f)$.
