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.

Answer 1

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