In Big-O notation, I often see something along the lines of
This algorithm is $\mathcal{O}(4n)$, but this can be reduced to $\mathcal{O}(n)$
While I understand that the idea of an algorithm being constant, linear, polynomial, etc. is important, for a sufficiently large $\kappa$, in $\mathcal{O}(\kappa n)$ where $\kappa$ is a constant coefficient, would it be a misrepresentation to reduce to just $\mathcal{O}(n)$? Consider an algorithm that is $\mathcal{O}(100n)$. If the size of the array being processed by the algorithm is $n=50$, then a purely $\mathcal{O}(n^2)$ algorithm, would actually entail fewer operations ($2500$) than the $\mathcal{O}(100n)$ algorithm would entail ($5000$). So my question is
- Why is this reduction allowed?
- Is there a sufficiently large value of $\kappa$ such that $\mathcal{O}(\kappa n)$ should not be reduced to $\mathcal{O}(n)$?
Best Answer
I'll answer 2 first: No, there is no sufficiently large constant $\kappa$ such that $O(\kappa n) \neq O(n)$.
Now, I'll answer 1: Why do we ignore constants in asymptotic analysis?
Different computers with different architectures have different constant factors. A faster computer might be able to access memory faster than a slower computer, so faster computers will have a lower constant factor for memory access than slower computers. However, we're just interested in the algorithm, not the hardware, when doing asymptotic analysis, so we ignore such constant factors.
Also, slightly different algorithms with the same basic idea and computational complexity might have slightly different constants. For example, if one does $a(b-c)$ inside a loop while the other does $ab-ac$ inside a loop, if multiplication is slower than subtraction, then maybe the former will have a lower constant than the latter. However, often, we're not interested in such factors, so we'll ignore the the computational complexity of addition and multiplication.
As $n \to \infty$, constant factors aren't really a big deal. Constant factors are very small in the face of arbitrarily large $n$.
This doesn't mean we always ignore constant factors: Randomized quicksort, which is worst case $O(n^2)$ but average $O(n\log n)$, is often used over the version that has worst case $O(n\log n)$ because the latter has a high constant factor. However, in asymptotic analysis, we ignore constant factors because it removes a lot of the noise from hardware and small changes in algorithms that really aren't important for analysis, making algorithms easier to compare.