1
$\begingroup$

This is my fifth question in an attempt to figure out what $f(n) \in O\left(n^2\right)$ actually means. I'll try to make it as simple as possible.

Facts I'm already aware of:

  1. Definition of Big O.
  2. If we have two functions from different Big O sets, we can figure out which one is going to eventually be bigger.

What we're given (in my question):

  1. We're given some algorithm that takes $f(n)$ steps in the worst case. And $f(n) \in O\left(n^2\right)$.

Preliminaries:

  1. I showed visually in What does the word "scalability" mean in terms of Big O? that you never know how exactly function $f(n)$ scales in the sense that the ratio $\frac{f(2n)}{f(n)}$ can differ significantly from $\frac{\left(2n\right)^2}{n^2}$ for any value of $n$ (no matter how large $n$ is) despite the fact that $f(n) \in O\left(n^2\right)$.
  2. In simple words it just means that the statement: "Double the input size $\implies$ quadruple the runtime" can't be taken on faith just from knowing that $f(n) \in O\left(n^2\right)$.

We often encounter statements like these:

  1. Function $f(n) \in O\left(n^2\right)$ grows / scales quadratically.
  2. For function $f(n) \in O\left(n^2\right)$ we know that if we double its input size, then its runtime is going to quadruple (assuming $n$ is large enough).

Question:

We already showed that you can never know how your algorithm's runtime will increase if you double (or just change somehow) the input size. Then what do statements like these mean? Are they referring to the function $f(n)$ itself or maybe to its upper bound? Here's what I mean:

  1. Do they (statements) assume that $f(n) = kn^2$ for some value of $k$ and then talk about how $f(n) = kn^2$ scales? Meaning, instead of finding the ratio of $\frac{f(2n)}{f(n)}$ you can just find the ratio $\frac{\left(2n\right)^2}{n^2} = 4$ and then you can say: "Double the input size of your algorithm $\implies$ quadruple the runtime". But then it's just an approximation and, moreover, it can be very wrong, since we know nothing about $f(n)$ itself except for the fact that $f(n) \in O\left(n^2\right)$. If that's the case, then why do people trust this approximation if they don't even know how wrong or right it is?
  2. My second guess (that might be useless though) is that statements like these refer to the upper bound itself. I mean, since we know that $f(n) \in O\left(n^2\right)$, then we know that eventually $f(n) \leqslant Cn^2$ for some constant $C$. From here we can talk about how the upper bound $Cn^2$ scales. If that's the case, then I don't understand why it even makes sense to talk about how the upper bound scales?

I'm not asking why people write such statements. I'm just asking what they mean exactly. Though I admit some of these statements might be wrong. Whatever. I just want to understand it right. Thank you in advance!

$\endgroup$
16
  • $\begingroup$ (Assuming $f$ is positive from now on.) $O(n^2)$ only is a statement on the upper bound of $f$, so it tells you not much about $\frac{f(2n)}{f(n)}$. If you instead know that $f\in \Theta(n^2)$, then you can indeed conclude that $\frac{f(2n)}{f(n)}\in\Theta(1)$, i.e. $$0<\liminf_{n\to\infty}\frac{f(2n)}{f(n)}\le\limsup_{n\to\infty}\frac{f(2n)}{f(n)}<\infty.$$ I am not sure if this can be improved (consider a function fluctuating a lot around $n^2$ or something like that, then $f(2n)/f(n)$ will every once in a while deviate a lot from $4$.) $\endgroup$ Sep 23 at 23:30
  • $\begingroup$ @Maximilian Janisch, Thank you for your reply and this example! But could you elaborate a little bit in the answer? I mean, what is meant by all these "scale" parts in such statements? $\endgroup$
    – mathgeek
    Sep 23 at 23:43
  • $\begingroup$ I will add a small reply soon. $\endgroup$ Sep 23 at 23:44
  • $\begingroup$ @Maximilian Janisch, Okay, thank you) $\endgroup$
    – mathgeek
    Sep 23 at 23:44
  • 1
    $\begingroup$ @MaximilianJanisch Right... Are you just saying that it matters how you sample for the average? If so, I agree, even if something I said made you think otherwise... My main point has been that if you want a generalization to work, then you have to devise it correctly (even if such a workable generalization is non-intuitive to some). $\endgroup$ Sep 24 at 0:18
3
$\begingroup$

First a few formal facts, afterwards I will give my interpretation. I will always assume that the function $f$ is non-negative.

  1. Let $M\in]0,\infty[$ and let* \begin{split}f:\mathbb N&\to\mathbb R,\\ n&\mapsto n^2(k(M)-(n\mod 2)),\end{split} where $k(M)\overset{\text{Def.}}=\frac{M}{M-1}$. Then we have $f\in\Theta(n^2)$, and for any odd $n\in\mathbb N$ we have $$\frac{f(2n)}{f(n)}=4\frac{k(M)}{k(M)-1}=4 M.$$ But $4M$ can be arbitrarily large (much larger than $4$, for example)!
  2. Indeed as mentioned in an answer to your previous question, we have $$\lim_{k\to\infty} \sqrt[k]{\frac{f(2^k n)}{f(n)}}=4$$ for any $f\in\Theta(n^2)$. (This follows more or less directly from the Definition.) This is no longer true for $f\in O(n^2)$ though. Consider for example $f(n)=n\in O(n^2)$, then the limit is $2$, not $4$.
  3. As mentioned in my comment, we have $$0<\liminf_{n\to\infty}\frac{f(2n)}{f(n)}\le\limsup_{n\to\infty}\frac{f(2n)}{f(n)}<\infty$$ for any $f\in\Theta(n^2)$. This fails once again if $f\in O(n^2)$, as for example $f(n)=\exp(-n)\in O(n^2)$ shows.

My interpretation is this: If you have $f\in O(n^2)$ and people say "doubling the input size quadruples the runtime", what they mean is that whenever you double the input size, then the worst time that you expect for $2n$ is less than the worst time that you expect for $n$. So when they write $f\in O(n^2)$, what they implicitly mean is that "I am prepared for $f$ to scale like $C n^2$ for some $C>0$, and so I am prepared for $f(2n)$ to be at most $4 C n^2$, which is $4$ times worse than the worst time that I am prepared for when it comes to $f(n)$."


* As a fun exercise: Try to write $f$ so that it is defined on all of $\mathbb R_+$, is smooth, and coincides on $\mathbb N$ with the $f$ above. (Hint: Try rescaling something like the cosine to replace $n\mod 2$.)


As a final remark: In practice, it is quite unusual to see erratic complexity functions as the one constructed above.

$\endgroup$
6
  • $\begingroup$ Thank you a lot for such a detailed answer! What you said in "My interpretation" part is basically this: if we double the input of $f(n)$, then the worst time is going to increase at most times $4$ (the actual runtime might increase much more, though), right? Meaning, when we talk about scaling of the runtime of the algorithm, say $f(n)$, in terms of Big O, we actually talk about scaling of its upper bound (and not the algorithm's runtime itself), right? $\endgroup$
    – mathgeek
    Sep 24 at 0:28
  • $\begingroup$ @mathgeek Yes, I agree with your comment. $\endgroup$ Sep 24 at 7:51
  • 2
    $\begingroup$ @mathgeek Maybe a bit more precisely: When you write "$f\in O(n^2)$", this is a formal statement that says that $f$ grows asymptotically slower than $Cn^2$ for some $C>0$. It doesn't by itself say anything about what happens when you double the input. When people then talk about "scaling/doubling the input", they implicitly talk about the upper bound, not $f$ itself. This is because when you look at $f(2n)/f(n)$, it may be very large, because $f(n)$ can always be "surprisingly fast". (I.e. you prepare for $f(n)$ to be as bad as $Cn^2$, but it ends up being better.) $\endgroup$ Sep 24 at 7:58
  • $\begingroup$ I think the grows asymptotically slower part is very important technically speaking; I don't really see how a statement such as "if we double the input of $f(n)$, then the worst time is going to increase at most times 4 " makes sense since $f(n)\in O(n^2)$ does not tell us anything about for which $n$ the growth is bounded by $Cn^2$. $\endgroup$
    – Paradox
    Sep 24 at 9:03
  • $\begingroup$ @MaximilianJanisch, And the word "asymptotically" means "in the neighbourhood of infinity, right? $\endgroup$
    – mathgeek
    Sep 25 at 20:41
1
$\begingroup$

In my limited experience in competitive programming, people often write $O(n^2)$ even if they actually know that the runtime is $f(n) \sim Cn^2$ for some $C > 0$, where $g(n) \sim h(n)$ means $\lim_{n \to \infty}\frac{g(n)}{h(n)} = 1$. In this case, $f(2n) \sim 4Cn^2$ so $\frac{f(2n)}{f(n)} \sim 4$. But you are right that if you interpret $O$ literally, then the bound might not be sharp enough to conclude that $\frac{f(2n)}{f(n)} \sim 4$.

$\endgroup$
3
  • $\begingroup$ Thank you for your reply! But I asked about something different. I asked about how the word "scale" is used and why it is even legitimate to use it, if we actually don't know what that ratio $\frac{f(2n)}{f(n)}$ is equal to. $\endgroup$
    – mathgeek
    Sep 23 at 23:18
  • 1
    $\begingroup$ Hmm, I think $f(n) \sim Cn^2$ is a rather strong statement if $f(n)$ is a runtime. The actual values of $f(n)$ are going to depend on very low-level details of the algorithm and model of computation, and such a specific $C$ may not exist. One of the big advantages of big-Oh notation is that you can elide some of these details. $\endgroup$ Sep 23 at 23:35
  • $\begingroup$ @JairTaylor It is stronger than $f \in O(n^2)$, but not too strong. Once you fix a software and hardware implementation, you can measure expected worst case time complexity. There often is a constant $C$. $\endgroup$
    – D. G.
    Sep 24 at 22:51
1
$\begingroup$

When we say that $f(x)\in O(x^2)$ we are already talking about a worst case scenario, since we are bounding the maximum value $f(x)$ can take. We are not interested on the exact time or the number of steps that an algorithm will take for each set of inputs, but we want to make sure that in the worst case (or the average case) our algorithm will be constrained. So, answering your question, scalability means: if we double the size of the input, then the runtime will be no more than 4 times the runtime of the worst case input for the original $n$.

In this sense, you are right about your second guess. It makes sense to talk about how the upper bound scales since the upper bound is a guarantee on the maximum number of steps.

Edit: After some discussion, I think I'm prepared to improve the answer.

First of all, let us assume that $f(x)$ is everywhere positive (to avoid division by 0), and that $f(x)\leq C x^2,$ so that $f(x)\in O(x^2).$

What does the big-Oh notation doesn't imply

The big-Oh notation doesn't tell us anything about $\frac{f(nx)}{f(x)},$ for any $x$, since $f(x)$ can have a very erratic behavior.

What does the big-Oh notation does imply

The big-Oh notation implies that $\left\{\frac{f(nx)}{n^2f(x)} \right\}$ is bounded above by a constant that is only dependent on the value of $f(x)$ and of $x$ itself, which is $\frac{Cx^2}{f(x)}.$ Indeed, notice that $\frac{f(nx)}{n^2f(x)}\leq \frac{C(nx)^2}{n^2f(x)}=\frac{Cx^2}{f(x)}.$

Thus, with respect to a certain pair $x,n,$ the big-Oh notation does not provide any information about the scalability of the original function $f,$ as the value of $\frac{f(nx)}{f(x)}$ can be arbitrary. But in general, we know that this value is bounded above by $Cn^2\frac{x^2}{f(x)},$ so we can't say that if you double the size of the input you will get 4 times the runtime, but we can say that if you double the size of the input, you will get $4k$ times the runtime, where $k$ can be controlled.

$\endgroup$
13
  • 2
    $\begingroup$ Thank you for the reply! But the "if we double the size of the input, then the runtime will be no more than $4$ times the runtime of the worst case input for the original $n$" part is WRONG. Consider function $f\left(n\right) = n^2\left(\cos (n) + 2\right)$. You can see that $f(n) \in O\left(n^2\right)$. But any ratio of the form $\frac{f(2πn)}{f(πn)}$ is equal to $12$. But you claim that it has to be less or equall to $4$. $\endgroup$
    – mathgeek
    Sep 23 at 23:32
  • $\begingroup$ @mathgeek Funnily I was just about to write an answer to your question with almost the exact example that you mentioned. Didn't you answer your own question basically? :) $\endgroup$ Sep 23 at 23:34
  • $\begingroup$ Well, there are a couple of considerations. First, few real life algorithms have such exotic functions. But, let us consider your example: the thing that is the most useful of this notation is that it smoothens our curve. For example, when we say that $n^2(\cos(n)+2)\in O(n^2),$ we are saying that $n^2(\cos(n)+2)\leq 3 n^2.$ Then, $3n^2$ is our worst case scenario. You can notice that $(n\pi)^2(\cos(n\pi)+2)\leq 3(n\pi)^2, \ (2n\pi)^2(\cos(2n\pi)+2)\leq 3(2n\pi)^2,$ and $\frac{3(2n\pi)^2}{3(n\pi)^2}=4.$ So this is what scalability means. $\endgroup$
    – Saat
    Sep 23 at 23:41
  • $\begingroup$ @Maximilian Janisch, I've just read your comment, yes :) It would be nice if you wrote an answer, since my question stays relevant. I mean, I don't understand what people mean by saying "double the input $\implies$ quadruple the runtime". I don't understand where this statement refers to. Or maybe they all just wrong to state such things? Or maybe they just approximate? It would be highly appreciated if you gave some examples as well. $\endgroup$
    – mathgeek
    Sep 23 at 23:43
  • 1
    $\begingroup$ @Saat, I've checked it, thank you! But what do you mean by "where k can be controlled"? And again: what is the point in knowing that "if you double the size of the input, you will get $4k$ times the runtime"? (you still don't know what $k$ is) $\endgroup$
    – mathgeek
    Sep 24 at 1:21

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.