What does Big O actually tell you?

Question

Two days ago I felt very uncomfortable with Big O notation. I've already asked two questions:

1. Why to calculate "Big O" if we can just calculate number of steps?
2. The main idea behind Big O notation

And now almost everything has become clear. But there are few questions that I still can't understand:

1. Suppose we have an algorithm that runs in $1000n$ steps. Why people say that $1000$ coefficient becomes insignificant when $n$ gets really large (and that's why we can throw it away)? This really confuses me because no matter how large $n$ is but $1000n$ is going to be $1000$ times bigger than $n$. And this is very significant (in my head). Any examples why it is considered insignificant as $n$ tends to infinity would be appreciated.

2. Why Big O is told to estimate running time in worst case? Given running time $O(n)$, how is it considered to be worst case behavior? I mean in this case we think that our algorithm is not slower than $n$, right? But in reality the actual running time could be $1000n$ and it is indeed slower than $n$.

3. According to the definition, Big O gives us a scaled upper bound of $f$ as $n \to +\infty$, where $f$ is our function of time. But how do we interpret it? I mean, given algorithm running in $O(n)$, we will never be able to calculate the actual number of steps this algorithm takes. We just know that if we double the size of the input, we double the computation time as well, right? But if that $O(n)$ algorithm really takes $1000n$ steps then we also need to multiply the size of the input by $1000$ to be able to visualise how it grows, because $1000n$ and $n$ have very different slopes. Thus in this case if you just double the computation time for the doubled size of the input, you're going to get wrong idea about how the running time grows, right? So how then do you visualise its growth rate?

I want to add that I know the definition of Big O and how to calculate it, so there is no need in explaining it. Also I've already googled all these questions tons of times and no luck. I'm learning calculus at the moment, so I hope I asked this question in the right place. Thank you in advance!

Answer 1

Reading between the lines, I think you may be misunderstanding Big O analysis as being a replacement for benchmarking. It's not. An engineer still needs to benchmark their code if they want to know how fast it is. And indeed in the real world, an $\mathcal{O}(n)$ algorithm might be slower than an $\mathcal{O}(n^2)$ algorithm on real-world data sets.

But, as $n$ approaches infinity, the $\mathcal{O}(n^2)$ algorithm will ultimately be slower. For the sake of example, if we allow constant factors in our Big-O notation, then an $\mathcal{O}(10n)$ algorithm will take more "steps" than an $\mathcal{O}(n^2)$ algorithm, if $n$ is less than $10$ ($10\cdot 10 = 10^2$).

But if $n$ is $100$, then the $\mathcal{O}(n^2)$ algorithm takes ten times as long. If $n$ is $1000$, it takes a hundred times as long. As $n$ grows, so too does this difference. That manner in which the two algorithms differ is what we are analyzing when we use Big O analysis.

Hopefully that example also makes it clear why the constant factor is irrelevant and can be ignored. Whether it's ten, a hundred, a thousand, a million, or a quadrillion ultimately does not matter, because as $n$ approaches infinity, the $\mathcal{O}(n^2)$ algorithm is eventually going to be slower anyway. That's the power of exponential growth.

The crux of it is that Big O analysis is a mathematical concept which does NOT tell an engineer how fast something is going to run or how many steps it's going to take. That's what benchmarking is for. Big O analysis is still a very helpful tool in algorithm design, but if you're interested in exactly how long something takes to run, you'll need to benchmark with real data.

Great summary in the comments from @chepner:

Put yet another way, Big O is not used for comparing run times, but for comparing how those run times scale as the input size grows.

Answer 2

Algorithms do not have a "speed". How fast a given algorithm runs in practice depends on the way it is implemented and the hardware and support software it runs on. So the speed of an algorithm does not depend just on the algorithm itself and thus is extremely difficult to analyze mathematically. For a given input, Algorithm A may run ten times faster that Algorithm B on one kind of computer, but only half as fast as B on another type.

So the "speed" of an algorithm is an ill-defined theoretical concept - in virtually all circumstances it can only be determined experimentally. Instead, the Big-O notation analyzes a performance-related property of algorithms that can be expressed mathematically: not its speed, but how well its performance scales. That means, Big-O does not tell you how fast an algorithm is in absolute terms, but only how its "speed" changes when you change the problem size (e.g. the number of elements to sort) . For example, for an O(n²) algorithm, doubling the problem size will increase the runtime four-fold while doubling the problem size for an O(n) algorithm will only double the runtime.

As a tool that is only supposed to answer questions about scaleabilty but not absolute absolute performance, constant factors do not matter, because they do not change the scaling behavior: An O(n²) algorithm will quadruple its runtime when doubling its problem size, no matter what the original runtime was. For example, for a problem set size of n=1000, one O(n²) algorithm may take one microsecond while a different O(n²) algorithm may take two hours. Big-O notification is not concerned with these absolute differences. It does tell you, however, that both will approximately quadruple their runtime when you double the problem set size to n=2000 - the faster of these two example algorithms from one microsecond to four microseconds, and the slower one from two hours to eight hours.

With that limitation in mind, Big-O it is not a replacement for speed measurements, but it is easier to obtain and useful enough in its own right to base certain decisions on without requiring experimental measurements.

Answer 3

You are right: The $O$ notation only tells you how big it is within a constant factor. If you want something more accurate than that, do not use $O$. The reason that $O$ notation is widely known and widely used is: it has been found useful over the years. Of course in some settings, other estimates may be more useful than $O$.

Answer 4

I think this has all been addressed before (on mse even!), but perhaps not in one answer, so I'll say a̶ ̶f̶e̶w̶ ̶w̶o̶r̶d̶s̶ (so much for "a few" :P) here.

For (1), I think you're misunderstanding the relevance of "dropping" constant factors and lower order terms. When we analyze runtime of an algorithm, we're doing it in some model of how computers work, and there's a variety of choices. We typically work with some version of the Word-RAM Model, but there's a smattering of low-level choices you can make. The notion of computation is extremely robust, but the notion of runtime isn't. We want to know that our notion of runtime doesn't care about which precise model we use, because different models model different facets of "real world" computers. Depending which model you use the precise constants in your runtime might change by constant factors, or might pick up lower order terms. This is analogous to not being able to tell exactly how many steps it'll take a computation to run, since that depends on the precise hardware you're running it on, as well as the specifics of how the algorithm is implemented (rather than the algorithm itself). What we can say, however, is that "up to lower order terms", the runtime is consistent. So we throw the lower order terms away, because they can be influenced by hardware or implementation details.

It still requires some justification, though, to know that throwing away constant factors "doesn't really matter", and this is why people often talk about how $1000n$ "isn't that much bigger" than $n$ whenever $n$ is extremely large. And I do mean extremely. If we take $n \approx 10^{10,000}$, then $1000n \approx 10^{10,003}$. In this case the difference really is tiny compared to the rest of the numbers involved.

Also, despite what they tell you in introductory programming classes the constants really do matter. We can't tell exactly what they are (for the reasons I mentioned above) but you can tell if your constants are $\approx 1000$ or if they're $\approx 2$, and you're entirely right in thinking those are different numbers!

In the real world, if you have a quadratic algorithm with a small constant and a linear algorithm with a huge constant, it's often better to use the quadratic algorithm because we'll almost never be running our code on inputs of size $10^{10,000}$. In fact, we're already doing this: There are a bunch of algorithms for which our theoretical big-O is smaller than the algorithm used in practice, yet the theoretical algorithm is never used because the constants involved are so massive. These algorithms are called galactic, and maybe knowing they exist will help you feel like you're not going crazy worrying about these things.

---

For (2), "worst case" refers to the worst of all possible inputs. For instance, say we want to write code that checks if a list has an even number in it. There's an obvious algorithm to do this

for x in list:
  if isEven(x): return True
return False

On the list $[2,3,4,5,6]$ this algorithm runs super quickly! Because the first element is already even. On the list $[1,3,5,7,9,11,13,14]$ it runs comparatively slowly, because it has to wait until the very end to see if an even number exists or not.

This does not have to do with $1000n$ being bigger than $n$. Remember that what we really care about is the runtime up to constants, because if you use a really crummy model of computation, or if you're really unlucky with which computer you use, you might pick up extra constant factors in your runtime without actually changing your algorithm at all.

This is in contrast to "average case" runtime, for instance. Here, instead of looking at the max of all the possible runtimes, we look at the average of the possible runtimes. As an example where this matters, you can show that quicksort takes $\approx n^2$ many steps in the worst case, but $\approx n \log n$ steps on average.

---

For (3), there's a substantial difference between, say, $n^2$ and $n \log n$ and $n$. Knowing how the runtime scales as your input scales is still a major factor in deciding which algorithm to use. For instance, to use the kinds of numbers you're worried about, say we multiply our input size by $10,000$. Does the runtime go up by a factor of $100,000,000$, by a factor of $10,000$ (plus an extra additive factor of $40,000n$), or by a factor of $10,000$? Obviously this matters a lot, and you can see that for inputs of size $1,000,000$ (which is tiny compared to some input sizes that real companies like google work with), an $n^2$ algorithm is going to be slower than a $1000n$ algorithm.

---

I hope this helps ^_^

Answer 5

The usefulness of comparison is this: No matter what you change the "parameters" you still arrive at the same general growth factor. Yes, 1000n is 1000 times larger than n. That is obvious. But what happens if you upgrade your cpu or run it on two threads? Then what? Well, REGARDLESS, the algorithms will STILL behave in the same way. n and 3n and 9n and 0.3432n all will behave in the same way regardless that the process runs" because the process depends linearly on n.

What we O(n) tells us is precisely how much time that the algorithm needs as it has to gobble up more and more data.

E.g., suppose you had an algorithm A that takes in a data set S and gives out T. We can represent that like T = SA where we can use reverse polish notation to express any complex of algorithms, e.g. 'T = SAB+RBAAA' where you can interpret the operations how you like(just read it from left to right).

Then that algorithms absolute performance might change with different cpus, say, if they are all in the same class under O(n) equivalence they all run the same(under equivalence, not absolute equality).

Think about it even more delicately: Let A_k be the algorithm at it's "kth step". Then another algorithm processing the exact same data would be the algorithm at the B_k step.

Then O(n) tells us that A_{k+1}/A_k and B_{k+1}/B_k are both the same class. O(n) is really the equivalence class for whatever family of functions that all grow at the same functional rate.

E.g., suppose that A_k takes 20 seconds to go to state A_{k+1} and 15 seconds to go from state A_{k+1} to A_{k+2}. Suppose we have a faster computer that runs A, which we will call B. Now B_k takes 15 seconds to go to state B_{k+1} and 11.3184 seconds to go from state B_{k+1} to B_{k+2}.

Then 15/20 = 0.75 = 11.3184/15.

That is, the same relative proportion of work is required by both machines. We compare just the algorithms, not the hardware they are running on.

Now, in reality, O(n) is not exactly what I have described above but it follows the same idea where we want to be able to say two things are the same even when they are not.

Why? Because in many problems we do not need to know the exact behavior of a function but only how it generally behaves. E.g., in convergence problems we maybe only want to prove something converges. In this case we don't need to know about local behavior. If we have a dominating function and know that the dominating function substitution operator is an identity on the limit operator then can compute and do limits much easier. Quick! What is the limit of 1/x*(cos(x)*3 + 1/x^cos(3x)) as x-> oo? Well, an application of mental O(n)-nastics can quickly tell one that it is probably 0. Rather than worry about all the junk after 1/x we can just use 1/x because, as far as the limit is concerned, they both are the same result(the limit sends them to the same equivalence class).

limit 3/x is the exact same as limit 2/x when x->oo. Just like $3x + 4$ is the exact same expression as 2x + cos(30.43Pi). They are both linear expressions. They are EXACT under that level of abstraction.

Here, we are doing the exact same thing but with function growth rates. But not their exact growth rates but their basic "shape". E.g., we can think of all lines as growing at the same rate. Same as all parabolas. Even though $3x^2$ technically grows faster than $x^2$ we consider them the same because the rate of growth change is actually constant with respect to the base function(think of the linear case). Of course then we can combine classes such as linear and quadratic terms. $x^2 + 3x$. Well, since we are concerned with large x and already proved that $x^2$ dominants $3x$(we can put in any more dominant form and still get a dominant form) we can say ignore "submissive" parts. E.g., $x^2 + 3x == x^2 == 3x^2 = x^2 + cos(3x) == ...$.

To recap if you take our algorithm A, it has a certain exact run speed that one could plot on a graph. But if you upgrade the hardware that graph will change. It will probably just look like a scaled graph though.

But say you run it now on a different OS and that different OS does different types of scheduling so your graph doesn't look quite the same. BUT it's same general pattern exists as before... at least for long run times!

So O(n) notation lets us talk about these issues more precisely. It's a way to classify the set of functions in to a useful partition/equivalence relation and then to apply them to find more useful consequences.

In your mind it is "Why are we making things so complex just to talk about run time performance? It makes no sense! Algorithm A takes 10 seconds to compute S and algorithm B takes 34.432 seconds to compute S! Algorithm A is better!". But that is not a useful metric. Why is A better? Just because it ran faster in your example? Maybe it is really not faster but just has better performance on small run times(small data sets) because it uses caching then becomes the worst algorithm on the planet. Then what? Knowing that A actually dominants B in O(n) tells us that B performs better in the long run.

By thinking in terms of O(n) you are thinking about more general ways that functions relate(it is sorta how with topology you can think about how different functions are equivalent(under homeomorphic transformations)). Also you are thinking more "futuristically" in that your "hardware" will upgrade automatically. E.g. if you design algorithms based on O(n) fundamentals then you can know if your algorithms are terrible or not no matter what machine they run on. As machines become faster the algorithms will still be the same "rank" compared to where they were before. So you are comparing algorithms sorta in their overall design and not one specifics that can change in any moment.

It's sort of like the inverse of Taylor. With Taylor series we add terms to get more and more terms = more and more precision. With O(n) we want to do the same but add less and get more dominance. E.g., 1 -> 1 + 2n -> 1 + 2n + n^2 vs 1 + 2n + n^2 -> 2n + n^2 -> n^2.

While the technical definition and usage has more "legalese" getting the idea down that this is something different and more useful is the key. Unfortunately they just give the definitions without explain why it was useful to create those definitions and most people then are taught the definitions RATHER than the experiences that led up to the definition. [E.g., they give you no or little context which means you are almost surely not going to understand it unless you happen to have some experiences that let you. ]

A large part of mathematics has a need to compare things in a "vague" way. That is, there is some overlap that we want to understand but the way we currently represent it makes it difficult to discuss. The machinery is then created to be able to transform(transformations are built) the problem in to a different way to think about it.

I.e., Once you realize comparing the performance of algorithms(which is just long term behavior in mathematics) is futile then you still need some way to compare them. The need to compare never went away, just the realization that the representation was inadequate. Hence a new representation is required and therefor a new language and that means definitions and their terms. When that is done for the algorithms we eventually get to the concept of simply representing(talking about) algorithms in terms of their longest "long term behavior". We do not care about initial fluctuation or minor aberrations... just the general long term behavior.

The definitions go about defining precisely what they mean by that.

Answer 6

What does Big O actually tell you? Edit: answering this question in the context of computational complexity, and not in general.

It tells you that if an algorithm is $O(f(n))$, then a physical machine can in principle be built such that the algorithm runs in either exactly $f(n)$ steps, or in the case where $f(n) = n$, arbitrarily close to $n$ steps.

Answer to the first question

I haven't seen anyone mention the main point here. All of the other answers are correct, that being asymptotic complexity is not a benchmarking tool. However, this doesn't answer the question of what asymptotic complexity is really useful for in the context of complexity theory.

You have to understand the original context in which this syntax was invented as it relates to algorithms. The idea is that this describes the performance of, not software, but machines. E.g. Turing machines. The Turing machine was a concept invented precisely to have an abstraction of computing machines in general.

What does this have to do with asymptotic complexity? Well, lets say you run your $O(n)$ algorithm on a Turing machine and it runs in exactly $1000n$ steps for any input string of size $n$. There is a theorem that says that a different Turing machine can be "built" such that the algorithm will take almost exactly $n$ steps to run.

In other words, although it is true that on any particular machine, it is possible for an $O(n)$ algorithm to in practice be slower than an $O(n^2)$ algorithm, what the theory of automata tells us is that it is always possible to build a machine such that the $O(n)$ algorithm will be in practice faster than the $O(n^2)$ algorithm, possibly at the expense of the performance of other algorithms.

So to answer your first question

Why people say that 1000 coefficient becomes insignificant when 𝑛 gets really large (and that's why we can throw it away)?

These ideas were historically developed with hardware engineering in mind, rather than software. They were also developed with the question of how fast a human could execute these algorithms with pencil and paper. If an algorithm takes $1000n$ steps to run, a physical machine can (in principle) be built such that the 1000 coefficient does go away, and the algorithm actually does take as close to $n$ steps as you want. The same goes for space complexity. Alternatively, if a human were to change their process slightly, they could run the algorithm in close to $n$ steps.

So when theoreticians develop algorithms, they develop them with asymptotic complexity in mind, because this is really the only way we can measure the resource requirements of an algorithm without specifying the machine it will run on. Essentially, without picking a particular "computer architecture" to run the algorithm on, they cannot make any meaningful claims about the coefficient of the algorithm's running time.

Obviously if you are developing real software, then you know more about the machines that it will run on, and can actually make decisions based on that. But when talking about algorithms in the abstract, this is not possible.

Answer to the second question

To answer your second question, this is to some degree convention, as other's have stated. However, it is important to note that worst case complexity is much easier to reason about than the others. This is because, in the theory of automata, the idea of 'time-bounded'-ness is really the only sensible definition without first bringing some form of universal probability in the mix. And thinking about best case performance is simply not as useful in the abstract.

For reference, time boundedness is defined in the following way

If for every input word of length $n$, $M$ makes at most $T(n)$ moves before halting, then $M$ is said to be a $T(n)$ time-bounded Turing machine.

The theorems that I mentioned in the first part of this answer are formalized with respect to time-boundedness. That is, let $f : \mathbb{N} \to \mathbb{N}$ be a function such that $f(n)/n$ tends to infinity as $n$ goes to infinity (in essence, $f(n)$ is non-linear). If a Turing machine $M$ is $cf(n)$ time bounded, then there exists some other Turing machine $M'$ which is $f(n)$ time bounded and computes the same function as $M$.

In the special case where $f(n) = n$, you can get very close to $n$, i.e. If $M$ is $cn$ time bounded, for any real $\epsilon > 0$, there is a Turing machine $M'$ which computes the same function as $M$ and is $(1 + \epsilon)n$ time bounded. The reason that it can't be exactly $n$ is simply because it will take at least $n$ steps to read the input.

This is the formal statement of what I was saying above about a machine being built that can make the coefficient 'go away'.

It is rather hard to even state these theorems with respect to any other form of time complexity other than 'worst-case' time complexity.

(The statement and full proofs of these theorems can be found in chapter 12 of Hopcroft + Ullman. This is the source of the quoted definition above).

So the reason that we use worst case complexity is really because it is the simplest and most useful way to talk about machines without introducing some notion of probability (as in the case of average time complexity).

Answer to the third question

This I think has been answered rather well by the other answers. But it is important to note that nothing about an algorithm being $O(f(n))$ means that this is the smallest asymptotic complexity that describes it. Again, the actual running time of an algorithm is defined really by time-boundedness as defined above, and these time bounds are put by $O$ complexity into asymptotic equivalence classes. The running time of an algorithm, even when you know the internals of a machine can only in general be given by an upper bound, it cannot be exact in general, since in general, creating a computable a function which takes as input a turing machine, and some input to the number of steps that the input will take to process is undecidable. If you restrict yourself to total recursive functions, then its a bit different, but still exact running time bounds for an algorithm are typically not very useful.

The time bound of an algorithm is just that, a bound. It can be a very tight bound or a very loose bound, and it's usefulness can vary depending on the 'turbulence' of the running time of the algorithm. So an algorithm which is time-bounded by $f(n) = 1000n$ or even $f(n) = n^2$ may in fact have a tighter bound of $f(n) = 2n$, or it may be the case that for every even number the algorithm has a least bound (up to asymptotic equivalence) of $f(n) = 2n$ but for every odd number its least bound (up to asymptotic equivalence) is $f(n) = 2^n$. This would then make the whole algorithm need a time bound of at least $2^n$.

Conclusion

I repeat the main point: that if an algorithm is $O(f(n))$, then what this means is that a physical machine can in principle be built such that the algorithm runs in either exactly $f(n)$ steps, or in the case where $f(n) = n$, arbitrarily close to $n$ steps.

Asymptotic complexity is less about software engineering, and more about the philosophical implications of finding an algorithm. It may be the case that with our current technology, an $O(n)$ algorithm has a time bound of $100000 n$ on most machines, but what complexity theory tells us is that in theory, it is possible for us to develop our technology in such a way that it takes essentially $n$ steps on most machines.

Answer 7

One example that I have always loved is at this web page:

http://www.batmath.it/matematica/a_taylor/pg8.htm

It is in Italian, but there is not much to read, I'll replicate it here. For the function $$ g(x)=\begin{cases} 2e^{-1/4x^2}\int_0^{1/4x}e^{4t^2}\, dt, & x\ne 0 \\ 0, & x=0, \end{cases}$$ the Taylor approximation actually worsens as the degree of the approximant goes up (see the pictures in the linked page - you have to click on "uno, due, tre, quattro, cinque, sei, sette" to see successive approximations).

The reason for this is that, even if $$ g(x)=P_n(x) + O(x^{n+1}), \quad \text{as }x\to 0, $$ where $P_n$ denotes the $n$-th degree Taylor polynomial, the constant implicit in the big-O depends on $n$. And for this specific example, the constant grows very fast as $n$ increases. Therefore, the approximation is good in a small neighborhood of the origin, but such neighborhood actually shrinks as $n$ increases, to compensate the growth of the implicit constant.

The bottom line is that you are right. The big-O means what it means: an inequality with an implicit constant. Omitting such constant can be psychologically great, but it does have its pitfalls.

Answer 8

1. Is significant $1000$ in $1000n$ or not is possible to say if we have same understanding of significance. From big-$O$ point view there holds $$O(1000n) = O(n)$$ So, they define same set.

2. $O(n)$ is not defined for estimation only for worst case. Where is this written? Roughly speaking it is set of functions who is better, then scaled $n$ in infinity neighborhood.

3. Visualization depends on who creates it and whether he/she will have the wrong impression how can we know it ?

Addition with answers to https://i.sstatic.net/OGY8L.png from chat https://chat.stackexchange.com/rooms/129614/discussion-on-answer-by-zkutch-why-to-calculate-big-o-if-we-can-just-calculate

To be pedantic knowing, that $g \in O(f)$ is not knowing nothing, because under "nothing" I understand, that information about $g$ is $\emptyset$. $g \in O(f)$ is very good info in some cases, is bad info in others, but is not "nothing".

To base properties and definition of big-$O$ on limit conception is not very good idea, because in a lot of cases limit of ratio $\frac{f}{g}$ does, not exists, but holds $g \in O(f)$. One decision is to use $\limsup$, but not to one based on limit. Let me here say more, that, personally I do not prefer the definition based on ratio $\frac{f}{g}$, as this form have no sense for $g$, which have subsequence of zeros.

With that said and moving on to your second paragraph let me say, that constant factor is insignificant in both cases: when we compare functions from one big-$O$ or from different. Big-$O$ "eats" constants in both cases.

Third paragraph. Why you need to emphasize word "ONLY"? May be somebody use, or will use, big-$O$ with some purpose, which do not mentioned yet.

Forth paragraph. Let's take some $O(F)$. If under "higher class" you understand such $O(G)$, for which $F\in O(G)$, then we can say nothing about $\lim\limits_{n\to\infty}\frac{g_1(n)}{f(n)}$ where $g_1 \in O(G)$ and $f \in O(F)$, because $O(F)\subset O(G)$. If we have $F \leqslant G$, then again $O(F)\subset O(G)$ and again limit of ratio probably doesn't exist or is any, if exists.

Write, please, here or in chat, if you find something not enough clear.

Answer 9

1. Big O is a mathematical concept allowing us to systematically discard information. By the definition, you can prove constant factors are ‘insignificant’ and do not affect the Big O of a function (exercise for you). This proof will tell you the meaning of ‘insignificant’ in this context: a heuristic for working out the Big O. But why not choose some other definition of Big O? Good question.

2. Big O actually does not estimate worst case running time. It is (sometimes) possible to model an algorithm’s contribution to the running time of some physical system by a function $f$ mapping ‘input size’ to number of ‘steps’. There is a lot of flexibility in choosing $f$. For a sorting algorithm, you could measure how many comparisons of pairs of elements are required on average for a list of length $n$, where the list elements are assumed to be independent and uniformly distributed. Now you could try to calculate $f$ exactly, or you could apply Big O. Then as a shorthand, you could say your Big O estimates an upper bound on average case running time.

3. You are right, Big O does not tell you anything about concrete running times. For an $O(n)$ time algorithm, doubling $n$ does not necessarily mean doubling time taken. Whenever you come across a new mathematical definition, it is helpful to build a list of examples. You say you know the definition of Big O and know how to calculate it, but do you have examples? (Keep in mind that terminology can be abused, keep track of those examples too.) $$ \begin{aligned} f(n) &= 1000 + n &\implies f \in O(n) \\ f(n) &= \frac{1000}{n} + \frac{n}{1000} &\implies f \in O(n) \\ f(n) &= \sqrt{n} &\implies f \in O(n) \\ f(n) &= 2^{1000n} &\,\,\,\,\not\!\!\!\!\implies f \in O(2^n) \end{aligned} $$

---

Okay, why not some other definition of Big O? Why discard information at all? Why not discard even more information?

First, the function $f$ can be too difficult to calculate exactly, even for the simple example of a sorting algorithm.

Second, often $f$ is already an imprecise measurement of reality, and therefore using Big O is a more truthful description. A ruler measures in millimetres, so give your measurement in millimetres with a confidence interval. Similarly, if you don’t know what machine your algorithm will be running on, give your algorithm ’measurement’ with Big O and Big Omega.

Third, there are alternatives. Soft O discards logarithmic factors. In practice, Big O finds the right balance in most situations. There are also ways to use Big O in increasingly refined estimates. For example, $\ln(n!)$ is trivially in $O(n \ln n)$, but Stirling’s approximation gives $\ln(n!) = n \ln n - n + O(\ln n)$. I think this usage of Big O is more common in real analysis than algorithm design.

In any case, if you already have exact descriptions $f(n) = n$ and $g(n) = 1000n$, and they are not modelling the real world, then Big O is not the tool for you.

Answer 10

As already stated, big O does not measure speed; it measures ability to scale. So it is most useful in comparing algorithms in different scaling classes. For example, for large data sets, a loglinear ($\mathcal{O}(n\log n)$) sort (e.g. quicksort) will outperform a quadratic ($\mathcal{O}(n^2)$) sort (e.g. insertion sort). So people who have to handle large data sets use quicksort rather than insertion sort. But big O doesn't tell you whether insertion sort is faster than bubble sort. And it especially doesn't tell you how well it will handle your data. Bubble sort can be great at sorting almost sorted data. It does linear time validation. Insertion sort is simpler and faster than quicksort for small amounts of data.

In the question, you said

Suppose we have an algorithm that runs in $1000n$ steps.

That's actually rather hard to calculate.

Consider, I have a variable in my program that is globally accessible. I set it to some value. I do a whole bunch of things, enough that the variable is only stored in RAM, not in cache nor a register. I want to add one to that variable. How many steps is that?

You might point out that there is literally an instruction for add one to a variable (let's just assume that one exists for that platform). But that instruction assumes that the variable is in a register. So we need to load the variable into a register. Hey, we have an instruction for that. But that instruction assumes that the variable is in cache. Ignoring different levels of cache (and paging out to disk), we need to load the variable from RAM. But it turns out that we don't actually have an instruction for loading a single variable from RAM into cache (much less a register). What we have is the ability to load a block of RAM into cache.

OK, this is more complicated than it seemed at first. But we're still game. We figure out which block of memory contains the variable. That might take some steps of its own to do, let's say five. Then we issue the load instruction. Now we find out that because RAM is slower than cache, this instruction takes multiple steps to finish. Something like start loading, ninety-eight wait steps, finish loading. If we have other work, we can do that instead of the ninety-eight wait steps. But let's assume that we can't do any other work until we have this variable incremented.

Eventually we have the variable's value loaded into cache. Now we need to issue another command to load it from cache into a register. So we do that. It turns out that that takes another ten steps worth of time. Once in register, we can increment it. There's 116 steps to do one line of code. And that was a really simple line of code.

Once we have the incremented value, we can use it for whatever it was that we needed. Let's figure on another ten steps. Now, we want to increment it again. Do we need another 116 steps? No, it's already in register. We can do the same instruction in a single step. So we've incremented the value twice in a mere 127 steps. Of which 115 were just to get to the point of starting. But from the perspective of the code we wrote, that was the same high level instruction. So how do we turn high level code into steps?

We can't just count lines of code. Some lines will take more work than others. We can't even be sure how many steps identical lines of code might take. Sometimes a simple increment might take one step. Sometimes 116. (And I entirely ignored writing the value back to RAM.) It's really hard to count the number of steps in code that is compiled or interpreted. Hard enough that we rarely even attempt it. It's far more likely that we'll use a profiler or benchmarking to measure the time it takes to run a program.

Big O doesn't care though. It just assumes that the time will be relatively consistent. Such that doubling the size of the data may double the time it takes to run. Or quadruple it. Or increase it by about 40%. Or triple it. It will usually be faster to use the smaller big O. And for those times when it isn't, we can fall back on profiling and benchmarking. But it's been very rare that I've tried to count the number of steps, and never professionally. That's the kind of analysis that tends to get done academically for illustration purposes. It doesn't really work in actual programming. Because compilers and CPUs are much more complicated than just processing steps.

In fact, they are more complicated than this example. In particular, the idea of "wait steps" between start and end steps is somewhat questionable. But that illustration makes it easier to think about what is happening, even if not a precise description of what actually happens.

Big O primarily helps by getting programmers to avoid the real flubs, e.g. calculating the Fibonacci sequence recursively as a binary tree. We have a rather straightforward linear time solution, a more complicated constant time solution for a single value from the sequence, and an elegant but exponential time recursive solution. I can't think of a circumstance where we want the exponential time solution (other than demonstrating that it is slow). But either the linear or the constant time solutions might be optimal for a given use case.

If you really need to optimize a program, you can't stop with big O. You need to carry on with profiling and benchmarking. Big O helps avoid some big mistakes. But there are plenty of mistakes that it will never catch.

Answer 11

Big-O isn't intended to tell you exactly how long some algorithm would take to run. It's meant for comparing algorithms and to give you some rough idea of running time that:

• is independent of the difference in running time between e.g. a comparison and an assignment
• doesn't care whether you're running it on a toaster or a cluster of supercomputers
• doesn't care how the constant factor might change for different input sizes
• is a fairly simple and clean representation (the exact running time of an $O(n^2)$ algorithm, as defined by e.g. number of comparisons, might actually be something like $20n^2 + 304n + 2587$, which doesn't roll off the tongue so nicely)
• is often easy to calculate

Most of those things wouldn't be true if you try to come up with something that tells you exactly how many seconds some algorithm takes to run.

In practice, constant factors usually aren't that big.

So, even though this may not necessarily technically be true for any given real-world input size, you can be fairly sure $O(n)$ will be faster than $O(n^2)$ for a large input size. It generally makes sense to pick the algorithm with the smallest big-O once your input size gets above a few hundred or thousand elements (although there may also be other considerations that would affect the decision, like how easy it is to implement), and to pretty much always try to avoid exponential time algorithms if the input size is greater than like 10-20.

It also often isn't too unreasonable to make statements like these: (although I would take them with a grain of salt, and take into account that they may become wildly inaccurate in a few years)

On the average modern computer, if you have an input size of $10000$ elements:

• $O(n)$ would take in the order of milliseconds.
• $O(n^2)$ would take in the order of seconds.
• $O(n^3)$ would take in the order of minutes.
• $O(n!)$ would outlive us all.

If you're using a supercomputer, you can likely divide the running time by 100, if not more. If you're using a toaster, you may need to multiply it by 100. But it's probably safe to assume you can't go from taking a few centuries to taking a few milliseconds by just using a different computer.

Using guidelines like the above, one should be able to get some idea of whether some algorithm is going to finish within some maximum running time for some given input size in production long before even writing the first line of code.

Something else you point out that's helpful:

We just know that if we double the size of the input, we double the computation time as well.

This is also just a rough guideline. An $O(n)$ algorithm can take e.g. $50n$ steps when $n = 100$, but $1000n$ steps when $n > 100$. But it is a good rule of thumb.

If you run the algorithm for 100 elements, you can work out about how long it'll take for 1000000 elements. This means you can run an algorithm for a small sample that takes a few milliseconds to figure whether you're going to need to wait minutes, days or centuries for the algorithm to finish if you run it on your actual input.

We rarely care about visualising growth rate in practice. We reason about it on a more theoretical level.

Note: big-O is an upper bound, not a worst case, and $O(n)$ says the upper bound is $cn$ (for some constant $c$), not $n$. So it's still entirely true for an algorithm that takes $1000n$.

Answer 12

So many answers but I don't see theta mentioned anywhere, so I'll touch on that.

Why Big O is told to estimate running time in worst case? Given running time O(n), how is it considered to be worst case behavior? I mean in this case we think that our algorithm is not slower than n, right? But in reality the actual running time could be 1000n and it is indeed slower than n.

As others have touched, $O(n)$ is a family. It says — if the input is k times larger, the running time is [at most] $k$ times larger. And $O(n^2)$ is another family where $k$ times larger input produces [at most] $k^2$ longer time.

Did you notice the square brackets? The thing is that $f \in O(g)$ does not mean that $f$ grows similarly to $g$. It means it grows no faster. For example, $x \in O(x^3)$ and $x^2 \in O(x^3)$. It just bounds your function from above, nothing more.

If you wanted a more accurate estimate, it's called Big Theta. The set $\Theta(g)$ contains all functions that are bounded above and below by $g$. E.g. $f \in \Theta(n^2)$ means that for $k$ times larger input $f$ is (at least and at most) $k^2$ times larger.

There's also the Big Omega which bounds from below, i.e. means "at least this slow". See https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations

Answer 13

I'm answering this from a more CS-y perspective, but also include a small numericy bit at the end.

1. There's two points here. The first one is because this factor becomes insignificant in contrast to $n$ if n gets big enough. Once you're dealing with $n=10^{{10^{10}}^{10}}$ is just doesn't make a real difference if there's another factor of 1000. And the second one is that we usually use big-O to differentiate between different classes; maybe it helps to think about this via some proxy like a measurement: let's say you have two rulers, one is a nanometer long and the other one is 1000 times as long - so a micrometer. If you wanted to measure a football court with these rulers this factor of 1000 would of course still be a thing - but compared to a laser-range finder that immediately tells you the distance they'd both be useless.
2. This also ties into how we use it. The factor doesn't make a real difference for large enough values of $n$ (note that when comparing algorithms for actual practical usage it often times is not enough to compare their "growth classes" with big-O but you'd actually have to consider the factors and the values of $n$ you'd reasonably expect) and if you were to compare it with another algorithm that's in an entirely different class this is even more so the case. So if you compare a function in $O(1000n)$ with another one in $O(x^2)$ we just say that the $O(x^2)$ grows so much faster that the $1000$ up front doesn't make a real difference. So we usually use big-O to talk about functions that are in entirely different leagues so to say.
3. This basically is the same thing again. Yes, the lines $f(n) = n$ and $g(n)=1000n$ have different slopes but they're constant in both cases. If you instead took $h(n) = n^2$ then at just $n=500$ the growth of $h$ would be just as bad as $g$ but it'd just continue to get worse and worse as $n$ grew on. Let's say you drew these slopes into a plot and started zooming out. The lines for the linear functions $f$ and $g$ would get closer and closer but they'd grow ever more different from $h$.

So all in all you're right that big-O notation isn't really useful when comparing functions inside one class. But that's not where we use it; we use it to compare between different . Let's say I write a taylor expansion $\sin(x) = x + O(x^3)$ then I really wouldn't care if there were a $1000$ in front of that $x^3$ - if I plug in $10^{-9}$ for $x$ I get basically $0$ in either case which is probably everything I'm really interested in. If the expansion was $x + O(x)$ this would be bad because then $x$ and this term I wanna neglect may be on the same order of magnitude so maybe at this point I'd start getting interested in the factor.

Answer 14

1. It does not get insignificant, it is simply ignored due to the definition of $O$, or, put in another way, "insignificant" depends on your definition. Say you have $f(n) = n$ and $g(n) = n + 1000$. In a sense the difference between the two functions is significant for low values of $n$ but stops being so for larger values as their ratio tends to 1. However, their difference is still 1000 and nobody dictates that only the ratio determines the difference between them.

   $O(n)$ is all about classifying functions into groups that accurately reflect their behaviour, but there can't be too many of them. If $O(n)$ and $O(1000n)$ were different categories, you'd have a lot harder time working with $O$, so it's simply practical to ignore addition and multiplication altogether. It's also reasonable, since you get neat classes like all linear functions, all polynomials of degree 2, 3 etc.

   Getting back to the difference of functions, taking their ratio is meaningful only within a single $O$ class, as comparing functions from different classes makes their (arithmetic) difference tend to $-\infty$ or $+\infty$ and their ratio tends to $-\infty$, $0$ or $+\infty$. $O$ is necessary to compare functions beyond what we were able to do before, to get some sense of their difference. There is no need to invent a new notation when the ratio is still sufficient.

2. One confusion here is that $O$ is actually for classifying functions, not algorithms. However, algorithms have certain properties that are functions, like the worst/best/average-case running time per unit of input, but also the additional space they need, expressed similarly. Worst-case time complexity is usually implied, but it's still one of the many. It's also the most useful anyway, as you get an upper bound on what time the algorithm may take

   Indeed $1000n$ is worse than $n$, but the "worst-case" part relates to the possible input of the given algorithm, not the $O$ approximation. Simply remember that $O$ classifies functions and an algorithm has many functional properties.

   Also notice that ignoring addition and multiplication makes $O$ scale-invariant. It doesn't matter whether the range of the function is in seconds, hours, bytes, kilobytes, kelvins or degress Celcius, you can safely ignore it.

3. $O$ is definitely useful for measuring algorithms, but it is also definitely not enough. Knowing the $f(n)$ for a $O(f(n))$ class gives you only an idea of what function to use when approximating the original function, but you still need to know the additive and multiplicative constants in practice. But knowing $f(n)$ makes it simple – the approximation is just $af(n)+b$. Indeed there are many algorithms where $a$ and $b$ do matter when compared to others, despire their complexity expressed using $O$ is better.

Answer 15

My way to answer :
Big O notation is not about the absolute amount of steps for $n$ but it is about the rate it grows.

A fun exemple to explain it is Galactical Algorithm, these algorithms technically have a really low O notation compared to similar problems BUT are absolutely unusable for everyday problems. For exemple, the most efficient way to multiply two integer is to do a Fourier's transformation with 1729 dimensions. It doesn't seem reasonable at all to use this algorithm, but with number with more that $10^{{10}^{38}}$ digits, it's actually more efficient than the classical multiplication.

So, lower O notation doesn't mean the algorithm is faster for your own use of it, it just describes how it evolves with larger amount of data. And a comparison between $n$ and $1000n$ is not revelent for comparing this way because it is a constant.

Answer 16

I'm just going to briefly address item #2 (and let others address items #1 and #3).

2. Why Big O is told to estimate running time in worst case? Given running time $O(n)$, how is it considered to be worst case behavior? I mean in this case we think that our algorithm is not slower than $n$, right? But in reality the actual running time could be $1000n$ and it is indeed slower than $n$.

You have this backwards. Big-O does not inherently describe worst-case behavior; it may or may not. The decision to measure worst-case behavior, or best-case behavior, or average case behavior is made up front; Big-O is then the metric used to measure any one of those dimensions.

For example, consider the Quicksort algorithm. Per Wikipedia:

• Worst-case performance: $O(n^2)$
• Best-case performance: $O(n \log n)$
• Average performance: $O(n \log n)$

So you see that there are different Big-O values for different parameters being measured.

Answer 17

Mathematically speaking the big-$O$ notation describes a pre-ordering$~\preceq$ (which is like a partial ordering without anti-symmetry requirement) on infinite sequences of (usually positive, which in fact I will be assuming in the discussion below) real numbers, which depends only the asymptotic behaviour of the sequences. The relation $f\preceq g$ is written $f(n)=O(g(n))$ and expresses the fact that $f(n)$ does not grow much faster than $g(n)$ for sufficiently large $n$. It such that the the corresponding equivalence relation (which holds between sequences $f$ and $g$ when both $f\preceq g$ and $g\preceq f$ and is written $f(n)=\Theta(g(n))$) is fairly coarse, and this is intentional. Thus one can replace, for the purposes of comparison by$~\preceq$, a sequence by any other one in its equivalence class, and this allows simplifying the expressions for $f(n)$ by dropping insignificant terms.

One could define different pre-orderings for this purpose. The minimum requirement is that $f\preceq g$ whenever there exists $N\in\Bbb N$ such that $f(n)\leq g(n)$ for all $n\geq N$ (I'll abbreviate this as $f(n)\leq g(n)$ as $n\to\infty$). But if one takes that as the only cases where $f\preceq g$ holds, then the equivalence class of $f$ is extremely small: it consists of the $g$ for which $f(n)=g(n)$ as $n\to\infty$, in other words, which differ from $f$ only in finitely many places. Even adding a very slow growing term like $\log\log\log n$ to a fast growing sequence like $n!$ would give a non-equivalent sequence. It is reasonable to want to ignore (in the sense of staying in the same equivalence class) contributions added to $f$ that grow slowly relatively to $f$ itself. This can be achieved by comparing to a scalar multiple of $g$. In terms of the (upward closed) set of $C>1$ for which $f(n)\leq Cg(n)$ as $n\to\infty$, there are two valid choices to define "$\preceq$": (1) define $f\preceq g$ whenever this set is all of $\Bbb R_{>1}$ (equivalently: its infimum equals $1$), or (2) define $f\preceq g$ whenever this set is non-empty. No other choices lead to a transitive relation "$\preceq$", for instance requiring $C=2$ to be in the set fails to do so because then $(3n)_n\preceq(2n)_n\preceq(n)_n$ but $(3n)_n\not\preceq(n)_n$. As a side note, observe that $f=o(g)$ means that the set of all $C>0$ with the same property is all of $\Bbb R_{>0}$.

Both choices (1) and (2) make $f$ equivalent to $f+g$ whenever $g=o(f)$, thus allowing to ignore "negligible terms" in the expression for a sequence. Still (1) gives a considerably finer equivalence than (2) does, as no two scalar multiples of the same sequence are equivalent. You might feel inclined to think that is a good thing, since (as your question suggests) intuitively the sequence $f$ corresponds to a much better efficiency than $1000f$ (even though it won't buy you much when $f(n)=n!$; it would matter though for $f(n)=n$ or even more in case $f(n)=\log(n)$). But you would be forced to also consider $f$ to be strictly better than $1.00007f$, where the difference seems to be less of a big deal. The main reason why people prefer the option (2), which gives the actual definition of $O(f)$, is that option (1) obliges you to take into account minute details that are hard to estimate. For instance if a task is achieved by a simple loop iterated $n$ times where the time for a single iteration is constant or can be bounded in a manner that does not depend on the details of the iteration, then we can say the task is completed in $O(n)$ time with definition (2). However with definition (1) one would, first, need to introduce a unit of time such as a clock cycle, and, second, compute the precise number of these units for the loop body. But that depends on details such as the exact sequence of instructions that the compiler produces, and that is something most people don't want to bother about. This being said, one can try to first classify methods in the usual sense of $O(f)$, and then among methods that are equivalent for this method try to distinguish more and less efficient ones based on the constant factor that appears when comparing two of them. Knuth does so in many cases (as do people trying to promote quicksort, since it is the only way to make that algorithm shine in comparison to alternatives like heapsort), but this requires for a somewhat fair comparison things like counting steps after converting to machine code for some idealised machine.

So to answer the concrete questions. 1. although considering the constant factor among sequences that are equivalent in the big-$O$ sense can be relevant, it would be both too cumbersome to have to worry about changes to such factors when determining the efficiency class of an algorithm, and almost impossible to determining the precise constants in any neural and objective manner. 2. The big-$O$ method compares sequences, and does not care a bit about what these sequences measure. If they are sequences of worst-case efficiencies, then this is what the notation will express, but they could just as well be average (or even best-case) efficiencies. 3. Being an asymptotic measure, no big-$O$ estimate says anything at all about any concrete value $f(n)$: if you change that value arbitrarily, or finitely many of them, this changes nothing about the big-$O$ estimate. So already it is vain to expect any hard conclusions about isolated running time to be drawn from big-$O$ estimates. The fact that in addition no information is carried about a constant factor does not make it fundamentally worse; this is simply not what the big-$O$ calculus is intended for. If you want to compare concrete running times, forget about big-$O$ and run benchmarks. One of the aspects in the art of programming is to know when to worry about big-$O$ facts, and when not to.

Answer 18

The big-Oh in an expression like $f(x) = O(g(x))$ does not tell you anything about the magnitude of $f$ over a certain domain, but rather it tells you how fast $f$ is increasing/decreasing.

That is why, for instance, using big-Oh notation while quantifying the error in an approximation doesn't make any sense because it doesn't tell you anything about the magnitude of the error, but it tells you how fast the error is decreasing/increasing when the variable is approaching a certain value.

Answer 19

The formal definition of big-Oh notation is only defining an asymptotic upper bound on time complexity that holds for all inputs above a certain size. Normally, we are referring to worst-case time complexity, although we can describe other functions of the input size this way (such as finding the order of the best-case or average-case time complexity as a function of the input size, how much memory the program uses, etc.). That isn’t always what you care about. Frequently, we try to optimize for the best average performance based on what kind of data we expect to get, but the theoretical order of the time complexity is dominated by some corner case that rarely occurs, or the function with better asymptotic performance only catches up on input sizes too large to be relevant.

For an extreme case, an algorithm that always took exactly one million five hundred ninety-three years and ten days to find the answer would have ϴ(1) time complexity. It would thus be faster than one that took ϴ(log log log N) time for a big enough input, but it might be a lot more practical to use the algorithm that runs faster on mere gigabytes or exabytes of data.

Another well-known real-world example is sorting algorithms. Quicksort has O(N²) worst-case time complexity, whereas there are other sorting algorithms, such as Mergesort, with O(N log N) time complexity. In the real world, though, many programs prefer Quicksort despite its worse theoretical time complexity. This is because Quicksort’s higher order of time complexity only means there is some case, for data above some size, where Mergesort would beat it. But, often, we aren’t expecting to ever have to deal with those unusual cases, so we use the algorithm that we expect to be faster most of the time.

Alternatively, if your upper bound on the time or memory complexity is not a worst-case bound, it might not give you the guarantee of real-time performance or memory usage that you need. If your system runs very slowly on pessimal inputs that “almost never” happen, an attacker might be able to feed it pessimal inputs as a denial of service.

I also recall Linus Torvalds discussing patches he rejected for the Linux kernel despite their having “optimal” O(1) time complexity. This guarantees that, for some inputs of sufficiently large size, the O(1) algorithm would be best. But, often, that was only true for a very rare case or an unrealistically large input, and Torvalds felt it was more important to perform well in the most common cases.

Answer 20

From a practical standpoint, the number of steps are not important. Big O notation gives us insight into how much more time or space our algorithm will take if we increase our input.

• $O(n)$ tells us that when we double our input size we double the amount of time to solve the problem. If we triple the input size, it takes three times as long etc. Problems that are $O(n)$ typically involve iterating through some collection a fixed number of times.

• $O(n^2)$ mathematically tells us that the time necessary to process an input of $n$ elements takes us about $n^2$ calculations. Intuitively, this usually means we have a problem that requires us to iterate through a collection once for each element of the collection. This is okay for small problems but can lead to problems for large input. Consider that an input size of a billion would take about a second if the complexity were $O(n)$ and about thirty years for $O(n^2)$. If this doesn't seem likely, search for the percolation problem.

• $O(2^n)$ These problems are intractible because if you add one element to your input you double your time.

• $O(\lg{n})$ is great. Notice that I use $lg$ which is $\log_2$. This means an input size of a billion (~$2^{30}$) only takes about thirty calculations to complete. We can double our input and only require one more step to find the result. We see this in a binary search. If you add an entire copy of your tree to a common root you only require one more comparison to do your search.

These examples should give you an idea about why we use the notation. We are usually not concerned with the exact clock time or memory usage. We want to get an idea of how appropriate an algorithm is for a problem.

Answer 21

Big-$O$ is a coarse measure of order of growth. Its utility is in ignoring details. Likewise, the mean of a distribution ignores a great many details about a distribution while still providing useful information. Much progress rests on taking a complex thing and partitioning out what is important (or real) from what is fussy detail (or noise).

One might ask, "How is a factor of 1000 'fussy detail (or noise)'?" The slowest vaguely recent computers have clock speeds of a few kHz. The fastest, a few GHz. So a factor of less than a million is an issue of engineering, not an issue of algorithm selection. The principal use of Big-$O$ is in algorithm selection.

If you wish to compare two growth rates, in your GIF you should scale one of them to be of height $1$ -- "this order of growth is my reference against which all other orders of growth will be compared". In your GIF, if you scale $n^2$ to be your reference, then you see $1000n$ and $n$ decaying toward $0$ like $1/n$ (this use of "like" is "order of growth/decrease" and is fairly commonly used this way). Both $n$ and $1000n$ are eventually insignificant compared to $n^2$ and they are both insignificant in the same order of growth. Extending the GIF, to include $1000n^2$, this is scaled to height $1000$, which, while bigger than $1$, neither grows nor shrinks -- $1000n^2$ has the same order of growth as does $n^2$. If you throw $n^3$ onto this graph it grows of order $n$ when scaled by $n^2$. Of course, so do $2n^3$ and $1000n^3$.

One way to see that Big-$O$ is a coarse measure is to see what it takes to land outside $O(n)$. Notice that for every $\epsilon > 0$ there exists an $N_\varepsilon$ such that for all $n > N_\varepsilon$, $1000n < n^{1+\varepsilon}$. So any choice of power bigger than $1$ eventually dominates $1000n$. So if we are grouping growth rates by powers of $n$, $1000n$ lands in the "$n$" group. But Big-$O$ doesn't just group by powers of $n$, one simple ladder of functions distinguished by Big-$O$ is iterated exponentials. Big-$O$ distinguishes between $n$, $\mathrm{e}^n$, $\mathrm{e}^{\mathrm{e}^n}$, and so on. (For an example of a doubly exponential complexity, see "Buchberger's algorithm".) Big-$O$ distinguishes powers of $n$. Big-$O$ distinguishes iterated logarithms. In short, Big-$O$ distinguishes big differences in order of growth and ignores small differences. The cut-off between "big" and "small" is implicit in the definition of Big-$O$. If, in a particular application, a different cut-off is preferable, then use a different measure of order of growth.

Your second issue is with measuring worst case run time. Question: What is the run time of the prime detection algorithm: "Try dividing by 2, then 3, then 4, ... up to the square root of the given number."? It varies. For half of all integers, this algorithm stops after one division. For one-third of the remainder, it stops after two divisions. For one-fifth of the remainder, it stops after three divisions. In the worst case (i.e., the input is actually prime), the algorithm performs the worst case number of divisions. If your summary of the algorithm must warn when the run time can be long, then your summary needs to report the worst case time. Notice in this setup, we can also report average case time (although this calculation is hard). In general, for particular inputs, an algorithm can be much faster than its worst-case time. But always, it is no worse than its worst-case time, so if you can budget that time into your schedule, you can be sure to get an answer before it is required. (Similar comments apply to space complexity. If you can allocate the worst-case space for your computation, you can be assured that it will complete without aborting due to insufficient space.)

Your third item isn't set in the context in which these questions are actually asked. Typically, one implements an algorithm. One knows its worst-case complexity order of growth. However, the actual algorithm's time and space requirements are more nuanced than the order of growth. A particular implementation may have time complexity $10^{-3}n^2 + 53 n + 10^5$ (loosely corresponding to "actually doing the work" ${} + {}$ "reading the input, scanning through lookup tables, and writing the output" ${} + {}$ "initialization and other fixed-overhead housekeeping"). When $n$ is small, this is dominated by the fixed overhead. When $n$ is medium, this is dominated by the linear activities. Once $n$ is large enough, only the leading, quadratic term matters. I suspect you have been thinking of monomial estimates of complexity, so have not thought through the real-world transition between orders of growth of different pieces of an implementation. Notice that the non-leading terms are something we can chip away at by varying the implementation -- perhaps we can make a snapshot of the initialized context and load that, reducing the linear and constant contributions to the complexity. The leading order term, however, is something we're stuck with. We can vary its coefficient by choosing different hardware, perhaps by up to a factor of a million. However, the two questions everyone wants answered are "how much time will this take to answer the questions we intend to ask?" and "how much worse will it be if we need to ask slightly harder questions".

The problem is all you usually know is "the algorithm that has been implemented is $O(n \log_2 n)$". So you run the algorithm on small, test problem instances to try to determine where the switchover from dominated by lower order terms to dominated by the leading term occurs and then a small number of larger test problems to ensure that the observed rate of growth is the same as the theoretical rate of growth. Notice that at no point is knowing the theoretical coefficient of the leading order term of any use at all -- it has been swamped first by lower order terms, then by the various implicit scaling factors inherent in the implementation. Once you know the empirical growth rate of your implementation (and assuming you know the intended input complexity), you can start to answer the two questions.

Answer 22

I might be able to help with the understanding. When you're looking at algorithms that run in memory, it's fairly straightforward to say $100n$ is faster than $1000n$. However, modern applications often work over networks. This can change your time efficiency to $100ln$ vs $1000ln$, where $l$ is latency. Testing often happens on a local network, where latency is very small.

Now, what happens when you have a different process where the time efficiency is $1000ln^2$? If you optimize your code to reduce $1000$ to $100$, that's nice, but if a customer changes $n$ from $100$ to $1000$, based on their data, your efficiency improvement is dwarfed by their data change. This is exactly what happened with one of my customers. We had a process that was $O\left(n^2\right)$, but didn't realize it. $n$ was frequently over a million, but the processing time was acceptable (overnight) when within the same state. Then a customer started the same process from the US to the UK, spiking the latency. Worse, the actual efficiency was something like $1000(ln)^2+50$, as $n$ represented a piece of data to transfer. Tinkering with the $1000$, or the $50$ was NOT going to fix anything. Changing it to $1000(ln)+100$ did. Going from $O\left(n^2\right)$ to $O(n)$ meant that ever increasing data didn't cause an explosive growth in the time to process.

I have also seen this happen in poorly designed SQL queries. Executing a $O\left(n^2\right)$ and a $O(n)$ query against a database with $100$ or $200$ records, you can barely tell the difference. When you deploy those same queries against a database with $10,000,000$ records or more, it changes from a query that takes an hour to process to a query that may take a week to process, and gets worse as you increase the record count.

As a reference, you may want to dig out a pre-calculus book and find the section on families of functions. The basic idea of Big-O notation is that, when zoomed out far enough, a family of functions all look about the same, aside from a scaling factor. Any algorithm that is dependent on user input/data/real-world factors is likely to violate your simple tests and behave very differently from what your calculations claim it "should". Changing the Big-O of your function will often do far more to protect you against that than any tweaks on the constants.