Question regarding $O(n^2)$ efficiency

Question

I'm going through a video of EDX course which talks about Big O notation. At the end of the video they have some questions but the $O(n^2)$ answer is confusing me. It feels like a mistake, but I just want to make sure.

The question is :

Imagine that we have a data set of 10 items. We run an algorithm on that data set, and it performs 10 operations.
Now imagine that we doubled the size of the data set to 20 items. Approximately how many operations might now be required if the algorithm is of...

• Linear order? 20

• Constant Order? 10

• Quadratic Order? 40

I don't understand why the answer if 40 if it's quadratic.

At first I thought it would be 400, because n2 is 400. But the drop-down answer menu doesn't have 400. The highest it has is 100.

So I thought it might be 100, because if 10 items take 100 operations, then increasing by 10, would increase by 100. However 100 seems to be wrong as well.

So why is the answer 40?

The course in question is here:

https://www.edx.org/course/introduction-computing-using-python-gtx-cs1301x Chapter 5.2

Answer 1

Say the time spent is some constant factor $c$ times $n^2$. Then we have:

$$c \cdot 10^2 = 10$$ $$c = 0.1$$

Thus then $c\cdot 20^2 = 40$.

Answer 2

It's easiest to remember how different asymptotic growths affect the outcome when n grows.

O (1) means: Growing n doesn't make a difference.

O (n) means: If n gets twice as large, it takes twice as long. If n gets ten times as large, it takes ten times as long.

$O (n^2)$ means: If n gets twice is large, it takes four times as long. If n gets ten times as large, it takes hundred times as long.

Of course if we are looking at asymptotics, all these things only work if n is large enough.

Still, with growth of $O (n^2)$ the numbers should be four times as large when n gets twice as large, so going from n=10 to n=20, the number of operations should go from 10 to four times as large, that is to 40.

Raphael's comment is of course right. Well, to some degree. Both $O(n)$ and $\Theta(n)$ are only valid for large numbers. So given the numbers for n=10, the outcome for n=20 is more or less guessing. We have $O(n^2) ≤ c\dot n^2$ and $c\dot n^2 ≤ \Theta(n^2) ≤ C\dot n^2$ for large enough n. n=10 or n=20 might not be "large enough" and we can't say anything about the outcome for n=20. And even if n=10 is large enough, there is still a wide range of values possible. We might have $0.01n^2 ≤ f(n) ≤ 100n^2$, and f(10) = 10,000, f(20) = 4 would be possible.