4

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

  1. Why is this reduction allowed?
  2. Is there a sufficiently large value of $\kappa$ such that $\mathcal{O}(\kappa n)$ should not be reduced to $\mathcal{O}(n)$?
Eli Sadoff
  • 450
  • 2
    look closely at the definition of an $\mathcal{O}(n)$ algorithm. –  Dec 27 '16 at 22:44
  • This is one reason why an $\mathcal{O}(n^{3/2})$ algorithm (for example) is not always preferable to an $\mathcal{O}(n^2)$ algorithm for an actual computation. If the constant coefficient is measurable and comparable between two algorithms, a different notation (not big-O) is sometimes used when comparing the algorithms. – David K Dec 27 '16 at 22:49

3 Answers3

6

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.

Noble Mushtak
  • 18,402
  • 28
  • 44
3

A non-negative-valued function $f$ is in $O(g(n))$ provided that there exists $k>0$ such that there exists $N\in \Bbb{R}$ such that $\forall n > N$ we have $f(n) < kg(n)$. This is to say, $f$ is eventually bounded above by some constant multiple of $g$.

Now, suppose $f\in O(4g(n))$. Then there exists $k$ as above such that $f$ is eventually bounded above by $4kg$. However, simply choosing $k' = 4k$, we see that $f$ is eventually bounded above by $k'g$, which is just another constant multiple of $g$. Thus, $f\in O(g(n))$. Further, $4$ could be replaced with any positive real number, no matter how large. It follows that we can drop constant factors without changing the meaning of the original statement.

As your example points out, big-O does not tell you everything about how "good" an algorithm is. Its purpose is to describe the long-term behavior. As an example, an algorithm not in $O(n)$ will always perform worse than an algorithm in $O(n)$ for sufficiently large n.

florence
  • 12,819
0

Definition: Let $g$ be a real-valued, real-input function. $\mathcal{O}(g)$ is the set of all functions $f$ for which there exist nonnegative numbers $M_f$ and $x_f$ such that $$f(x) \leq M_f |g(x)| \text{ for } x \geq x_f.$$

The simple result below answers both of your questions.

Lemma: Let $g$ be a real-valued, real-input function and $c$ be a positive constant. If $f \in \mathcal{O}(g)$, then $f \in \mathcal{O}(cg)$.

Proof: Suppose $f$ is in $\mathcal{O}(g)$. It follows that we can find nonnegative numbers $M_f$ and $x_f$ such that $$f(x) \leq \frac{M_f}{c} |cg(x)| \text{ for } x \geq x_f,$$ and hence $f\in\mathcal{O}(cg).$

parsiad
  • 25,154