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

  • 1
    $\begingroup$ The question is bogus. Landau notation does not allow you to make predictions like that; any of the three would be possible. $\endgroup$ – Raphael Jan 25 '18 at 21:21
  • 1
    $\begingroup$ Intuition behind the answer being 40 is: If you double the size of the input ($10 * 2= 20$) the operations needed is four times greater (square of two) ($10 * 4 = 40$). It can be confusing but note that in the first equation $10$ is the size of the input, while in the second equation is number of operations required. $\endgroup$ – Marcelo Fornet Jan 25 '18 at 22:56

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

  • $\begingroup$ While this is certainly the computation they wanted students to make, it has precious little to do with Landau-style asymptotics. $\endgroup$ – Raphael Jan 25 '18 at 21:21
  • $\begingroup$ @Raphael I fully agree, I was considering expanding my answer with that but I wouldn't know how to explain the nuance of why this calculation is essentially meaningless when all the information you have is 'it's $O(n^2)$' and two datapoints, while still acknowledging the educational value of doing a rough 'quadratic growth' calculation, and then putting that all in words understandable for (what I perceive to be) the knowledge level of the asker. So I just kept to the calculation asked. $\endgroup$ – orlp Jan 25 '18 at 21:28

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.

  • $\begingroup$ You want to use $\Theta$. $\endgroup$ – Raphael Jan 26 '18 at 0:01

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.