# What does the word "scalability" mean in terms of Big O?

I've encountered a lot of sources claiming that:

Benchmarks estimate runtime, Big O estimates scalability.

They explained the meaning of "scalability" as follows:

Scalability tells you how your algorithm runtime scales. Meaning, how the computation time grows when you increase the input size. For $$O\left(n\right)$$ you double the size of the input, and you double the computation time. For $$O\left(n^2\right)$$ you double the size of the input, and you quadruple the computation time and so on.

Meaning, if your algorithm takes $$f(n)$$ steps in the worst case and $$f \in O\left(n^2\right)$$, then the ratio $$\frac{f(2n)}{f(n)}$$ is equal to $$4$$ for large enough values of $$n$$ (you double the input size, and you quadruple the computation time).

And it made so much sense. But recently I've been shown a counterexample proving that the above statement is just wrong. Consider the function $$f\left(n\right) = n^2\left(\cos (n) + 2\right)$$. We can see that $$f \in O\left(n^2\right)$$. Moreover, for those of you who want to notice that by $$O\left(n^2\right)$$ people usually mean $$\Theta\left(n^2\right)$$ we can easily observe that $$f \in \Theta\left(n^2\right)$$ as well: But $$f$$ doesn't scale like $$n^2$$ in the sense that we can't claim that $$\frac{f(2n)}{f(n)}$$ is equal to $$4$$ (even approximately) for any (even large) values of n. I mean if we know that $$f \in O\left(n^2\right)$$ and if we double its input size, we can't just quadruple the computation time, because it's wrong.

I made a plot of $$\frac{f(2n)}{f(n)}$$ for you to visualise it: It doesn't look like this ratio is tending towards 4.

So, my questions are:

1. Why do people explain the meaning of "scalability" like that? Is there a reason for that or are they technically wrong?

2. What does this word "scalability" mean, then? What exactly does Big O estimate, then (if not "scalability")?

In general, I'm looking for pure mathematical explanation of that. But don't make it too difficult, please: I'm still learning a single variable calculus. Thank you all in advance!

• There is an issue in that the limits don't technically exist. It is clear that $f$ is $\Theta(n^2)$ by the boundedness idea, but the limit definition notes that while the ratio of the functions definitely is finite and non-zero, the cosine limit is undefined at infinity (oscillation). I'm unsure here, but there may even be grounds to say that $f$ is not $O(n^2)$ at all by this token. Sep 22 at 16:25
• @FShrike, Thank you for the comment. But $f \in O\left(n^2\right)$ by the definition of Big O. Sep 22 at 16:28
• The scalability idea is confounded by oscillation, but there is no immediate conclusion of scalability from the limit definitions (although I now recall the limit definitions use limit suprema and infima to get around the idea that the regular limits don’t exist, so I take back some of what I said in the previous comment) Sep 22 at 16:30
• 1. Examples like this where $f \in \Theta(g)$ but $f/g$ is oscillatory as $n \to \infty$ are not common in actual practice. Offhand the only thing that comes to mind with this behavior is the FFT, and even that has a fixed scaling if you work along powers of 2 only. 2. Scalability still expresses the growth rate of the function in a rough way, how much bigger does it get when you increase the input by a bunch. Big Theta still gives you this rough description. But you are right that just knowing, say, $f \in \Theta(n^2)$ doesn't tell you that $f(2n)/f(n)$ will tend towards $4$.
– Ian
Sep 22 at 16:31
• In the context of complexity theory in particular people usually care about either worst cases or typical cases. Worst cases in your situation would mean "compare two problems where $n$ is near a multiple of $2\pi$"; typical cases would mean "compare two problems where $n$ is near an odd multiple of $\pi/2$".
– Ian
Sep 22 at 16:34

This (very nice) example is quite unusual - in practice functions $$f(n)$$ that actually come up and are $$\Theta(n^2)$$ typically satisfy $$f(n)/n^2$$ tends to some positive limit (rather than merely being bounded away from $$0$$ and $$\infty$$). So the simplified version of scalability - $$\lim_{n\to\infty}f(2n)/f(n)$$ - exists and is $$4$$.

However, even for your function, there's still a reasonable sense in which doubling $$n$$, on average, increases $$f(n)$$ by a factor of $$4$$. What can we mean by "on average"? Well, to take an average you need to double more than once. If you double twice to go from $$f(n)$$ to $$f(4n)$$ then the average scaling factor of the two doublings that makes sense is the geometric mean (because you're trying to approximate by geometric growth), i.e. $$\sqrt{f(4n)/f(n)}$$. Now this doesn't tend to a limit either, but $$\sqrt[k]{f(2^kn)/f(n)}$$, i.e. the (geometric) average scaling factor from $$k$$ doublings, does tend to a limit as $$k\to\infty$$, which is $$4$$.

• Thank you for the answer! But doesn't it look like we just invented out of thin air a way to justify the original meaning of the word "scale"? Sep 22 at 18:11
• Also, why is the arithmetic mean worse in this case? It seems to me as much reasonable as the geometric mean is. Sep 22 at 18:34
• @mathgeek It's basically because if we scale by a factor $x$ and then scale by a factor $y$, then the overall scaling is $xy$ not $x+y$. The idea of taking an average is "what list of $k$ identical things would be most like this list of $k$ different things?" Here scaling by $k$ different factors should give the same overall result as scaling by the "average" factor $k$ times, and that works if as "average" means the geometric mean. Sep 22 at 20:07
• It's still correct, it just can fail at the level of the comparing two particular function values if $f$ is weird. And I really cannot stress enough how atypical your example is in real asymptotic analysis, especially in complexity theory.
– Ian
Sep 23 at 13:25
• @Jean-ClaudeArbaut I don't see why it's misleading. I'm specifically talking about OP's example, which (as OP specificially says) is an example of a function which is $\Theta(n^2)$ but appears not to scale as expected. If you only know a function is $O(n^2)$, then in the second paragraph you basically need to replace $\lim$ by $\limsup$ and $4$ by $\leq 4$. Oct 5 at 8:33

The Landau symbols do not care about the exact behaviour of functions. $$f\in O(g)$$ means that for large $$x$$ we have $$f$$ scales at most so bad as $$g$$ in the sense that $$f$$ is bounded by a multiple of $$g$$.

When people explain it the way you mentioned it they are oversimplifying it, probably assuming that the other side would else not understand what one is talking about.

• Thank you for the answer! But if you look at my first plot you will notice that $f$ scales worse than $n^2$ at interval $\left(10;\ 12\right)$ for example. Therefore, It doesn't "scale AT MOST so bad as $g$". Sep 22 at 16:35
• @mathgeek We consider limits as $n\to\infty$ in the standard definition, not as $n\to(10,12)$ Sep 22 at 16:36
• I just gave an example so you can easily observe it from the plot. But I'm sure you can see that my statement holds for any $n$ (you can make it as large as you want). Sep 22 at 16:39
• @mathgeek That is one of the caveats with Landau notation. Scaling is a term we use for the argument getting large, but we do not specify how large that would be. Note that if $f$ is continuous and $g$ is continous and nowhere $0$ then on any closed interval we always find a $c$ with $f\leq cg$ on that interval (min/max of cont. functions on compact sets). And even then, the definition of the Landau symbols always specifies: For all $x>x_0$ for some arbitrary $x_0$. So basically we do not care about finite values.
– Lazy
Sep 22 at 17:52
• You can think about this this way: If $f\in O(g)$ then the asymptotic $\limsup\frac{f(x)}{g(x)}$ is finite. If $f\in\Theta(g)$ then also $0<\liminf \frac{f(x)}{g(x)}$.
– Lazy
Sep 22 at 17:53