0

When I reading through an article about asymptotic notation, there is a sentence - "For large enough inputs, the multiplicative constants and lower-order terms of an exact running time are dominated by the effects of the input size itself."

I get the part about "lower-order terms" since when lower order terms will become insignificant when compare with highest order term. But why "multiplicative constants" will be dominated? Why get rid off it will make sense?

I means no matter how big that X is, there will always be a noticeable difference between 3X and X.

wintop6211
  • 103
  • However small your multiplicative constant is, you can make your variable large enough so that the whole term will be very high in magnitude. – Sarvesh Ravichandran Iyer Apr 05 '16 at 01:24
  • when you write that $f$ is differentiable at $a$ $\Leftrightarrow$ $f(a+x) = f(a) + x f'(a)+ o(x)$ it is obvious why the asymptotic notation is as it is – reuns Apr 05 '16 at 01:25
  • You're right though that the phrase "multiplicative constants ... are dominated" makes no sense. What is true is that in asymptotic notation, multiplicative constants are ignored. –  Apr 05 '16 at 01:32

1 Answers1

0

This is due to the definition of asymptotic notations. If $f:\mathbb{N} \to [0,\infty[$, we have $$ \Theta(f) = \{g\mid \exists (c_0,c_1 > 0\mid c_0 f \leq g \leq c_1 f )\} $$ Clearly $\Theta (\lambda f) = \Theta (f)$ for any $\lambda > 0$, since we can scale $c_0$ and $c_1$ proportionally to $\lambda$.

Henricus V.
  • 18,694
  • Yeah, I get the definition of asymptotic notations, but I means what the purpose to get rid off multiplicative constant. Why this definition let you do that? – wintop6211 Apr 05 '16 at 01:31
  • @wintop6211 It is often insignificant when $n$ becomes large. – Henricus V. Apr 05 '16 at 01:32
  • Sorry, my question may seems really silly, since I'm not good at math like you guys. But please explain by which way it become insignificant. When you have 3 * 10^6, it's much more huge than only 10^6, to me, 3 plays a big role here. Thanks. – wintop6211 Apr 05 '16 at 01:36
  • @wintop6211 Asymptotic notation deals with orders of growth. For example. $1000^3$ is $1000$ times larger than $1000^2$, while $3 * 1000^2$ is only $3$ times larger. – Henricus V. Apr 05 '16 at 01:41
  • That make sense to me, thank you! – wintop6211 Apr 05 '16 at 01:44