6
$\begingroup$

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:

enter image description here

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:

enter image description here

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!

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$
    – FShrike
    Sep 22 at 16:25
  • $\begingroup$ @FShrike, Thank you for the comment. But $f \in O\left(n^2\right)$ by the definition of Big O. $\endgroup$
    – mathgeek
    Sep 22 at 16:28
  • $\begingroup$ 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) $\endgroup$
    – FShrike
    Sep 22 at 16:30
  • $\begingroup$ 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$. $\endgroup$
    – Ian
    Sep 22 at 16:31
  • 1
    $\begingroup$ 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$". $\endgroup$
    – Ian
    Sep 22 at 16:34
5
$\begingroup$

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$.

$\endgroup$
6
  • 1
    $\begingroup$ 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"? $\endgroup$
    – mathgeek
    Sep 22 at 18:11
  • $\begingroup$ Also, why is the arithmetic mean worse in this case? It seems to me as much reasonable as the geometric mean is. $\endgroup$
    – mathgeek
    Sep 22 at 18:34
  • $\begingroup$ @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. $\endgroup$ Sep 22 at 20:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ian
    Sep 23 at 13:25
  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 5 at 8:33
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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$". $\endgroup$
    – mathgeek
    Sep 22 at 16:35
  • $\begingroup$ @mathgeek We consider limits as $n\to\infty$ in the standard definition, not as $n\to(10,12)$ $\endgroup$
    – FShrike
    Sep 22 at 16:36
  • $\begingroup$ 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). $\endgroup$
    – mathgeek
    Sep 22 at 16:39
  • $\begingroup$ @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. $\endgroup$
    – Lazy
    Sep 22 at 17:52
  • 1
    $\begingroup$ 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)}$. $\endgroup$
    – Lazy
    Sep 22 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.