Need explanation of GRE Big-O notation question

Question

I am looking for an explanation for this question since i'm studying for GRE:

An algorithm is run in 10 seconds for a size 50 entry. If the algorithm is quadratic, how long in seconds does it spend to approximately on the same computer if the input has size 100?

I can't see a relation between time and the input.

Considering: O(n^2) -> O(50^2) =! 10 (seconds)

Also, i would like to study more about this topic, so please add any source if you can.

Thanks.

This seems more fitting for the [Computer Science](https://cs.stackexchange.com) site. — Joseph Wood, Sep 24 '18 at 21:52

Margaret Bloom · Accepted Answer · 2018-09-25T06:59:39.930

Note that the terminology is sloppy, time complexity has no notion of time (yes, the name is deceiving).

Neglecting terms smaller than O(n²) since we are working under the big-O framework, a quadratic function can be expressed as

t = c * n²

Given the (t, n) pair with value (10, 50) we have

10 = c * 2500
c = 1/250 = 4/1000

Solving for (t, 100) we get

t = 4/1000 * 10000 = 40

There is a faster and more insightful way to solve this problem.
The trained eye can spot the answer as 40 immediately.

Consider this function power function:

t = c * n^k

Now lets consider the inputs m₀ and m₁, with m₁ = a * m₀ being an (integer) multiple of m₀.
Lets compare the respective t₀, t₁:

t₀ = c * (m₀)^k
t₁ = c * (m₁)^k = c * a^k * (m₀)^k

So we see that for a polynomial time function t₁/t₀ = a^k, or t₁ = a^k * t₀.

The ratio between two output is the ratio between their inputs, to the k-th power.

For a quadratic function k = 2, thus the ration between two outputs is the square of the ratio between two inputs.
If the input doubles (ratio = 2) the output quadruples (ratio = 2² = 4).
If the input triples (ratio = 3) the output is nine-fold (ratio = 3² = 9).

A good mnemonic trick is to remember that the function from the inputs ratio to the outputs ratio is of the same kind of the given function.
We are given a quadratic function so that is the kind of relationship between the inputs and outputs ratios:

input   output
ratio   ratio
 1       1
 2       4
 3       9
 4       16
 5       25
...      ...

The problem tells you that the output doubles (from 50 to 100 entries) so the output must quadruple (from 10 to 40) as the function is quadratic.
As you can see all the data from the problem is used elegantly and without any hardcore computation.

Suggesting out-site sources is frowned upon but in this case I can't help but recomending the reading of:

Introduction to the Theory Computation - Michael Sipser

See if you can answer these questions:

If the input is now 150 entries, how much time does it take?

90
If the input is now 30 entries, how much time does it take?

90/25 ~ 4
If the input is now 100 entries but the program is run in a computer that is twice as fast, how much time does it take?

20
What size of the input is necessary to make the program run for at least 1000 seconds?

500

Great explanation. I am a bit confused on the questions that you have asked. " If the input is now 150 entries, how much time does it take?" Why is the answer 30? Shouldn't it be 90? — karthick, Sep 24 '18 at 23:18
I also would like to know... using the formula described i got 90 instead of 30 — heresthebuzz, Sep 25 '18 at 00:29
@joann2555 It's 90, my bad. I must have copied the wrong number ;) — Margaret Bloom, Sep 25 '18 at 06:59
No problem, @MargaretBloom. But i can't understand the second question. Could you please explain? I know that 30 is 60% of 50 or 3/5. — heresthebuzz, Sep 25 '18 at 15:01
@joann2555 Then 3/5 is the ratio you have to square and multiply for the original input size ;) — Margaret Bloom, Sep 25 '18 at 17:07
@joann2555 It's the original time, t0. Sorry :) It's (3/5)^2*10 = 90/25 — Margaret Bloom, Sep 25 '18 at 18:01
@MargaretBloom could you please answer this other question of mine? https://cs.stackexchange.com/questions/97772/what-is-the-time-complexity-of-this-power-algorithm — heresthebuzz, Sep 28 '18 at 13:00
@joann2555 Unfortunately, I don't have an account on cs.stackexchange.com. However the people over there are very good at answering that kind of questions ;) — Margaret Bloom, Sep 28 '18 at 13:09
Oh, fine. Yes, i was concerned because none answered briefly. I checked wikipedia but the algorithm there is different and i couldn't figure out the order of that function — heresthebuzz, Sep 28 '18 at 13:17

score 1 · Answer 2 · answered Sep 24 '18 at 21:00

Given the time complexity you can't calculate the exact running time (in seconds) of the algorithm. However, it does give you a good idea of the growth rate of measured time.

In a linear time algorithm (O(n)), time is expected to increase linearly as a function of the input. For example, if 10,000 items take one second to process in some machine, then you should expect 50,000 items to take about 5 seconds, and so on. This isn't the case in a quadratic algorithm (O(n^2)), which "punishes" you more as the input size is larger; an increase of x2 in input size will result in x4 processing time, an increase x5 in input size will result in x25 processing time, etc (Just like the function F(x)=x^2 behaves).

You can use this post as an introduction, and this one as a more formal explanation.

score 0 · Answer 3 · answered Sep 24 '18 at 21:00

The Big-O doesn't inform you about the exact correlation between entry size and the execution time, but instead it tells what's the approximate correlation between the entry size growth and the execution time growth. So: O(n) complexity means that the entry size and the execution time are in direct proportion (if the input is 3 times bigger, then the execution time will also be 3 times longer), O(n^2) means that if the entry size is 3 times bigger, then the execution time will be 9 times longer etc.

In your case, the initial execution time for a size 50 entry is 10 seconds. If the input changes to a size 100 entry, then by simply dividing we can tell that it's 100 / 50 = 2 times bigger. Knowing that the algorithm's Big-O is O(n^2), we can tell that the execution time will be 2^2 = 4 times longer. So if the initial execution time was 10 seconds, then the execution time for the bigger input will be approximately 10 seconds * 4 = 40 seconds.

Related SO question: Rough estimate of running time from Big O

Nice article about the big-o: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Need explanation of GRE Big-O notation question

3 Answers3