Help Calculating Computer Time used by Algorithms

Question

Recently I have been working through a textbook question that states the following:

An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 (assuming that low-order terms are negligible) if the running time is

a. linear

b. O(N log N )

c. quadratic

d. cubic

Now I know how to get Linear as $500/100 = 5$ thus $0.5ms * 5 = 2.5ms$

What I don't understand is how do I scale this answer of 2.5ms linearly to quadratic, nlogn, and cubic? Are there theorems or expressions that I am missing?

The way I would go about $N^2$ is that $2.5ms^2 $ is 6.25 ms which is not the answer in the answer key(ans = 12.5). and i'm not sure what I would start with for $nlogn$

What does it mean when the question says this?

(assuming that low-order terms are negligible)

Any explanation would be appreciated.

Answer 1

When we say that an algorithm runs in $O(N \log(N))$ that means that there exists a constant $C$ such that the time of execution $T(n)$ (as a function of the size $n$ of the input) is such that $T(n) \leq C n \log(n)$. And this is not very precise. Often we implicitly mean that the algorithm runs in $\Theta(N \log(N))$, which means that there exists two constants $C_1$ and $C_2$ such that $C_1 n \log(n) \leq T(n) \leq C_2 n \log(n)$.

That being said, to answer your question we will consider that the running time of your algorithm is $T(n)=C n \log(n)$.

Then $T(500)= 500C \log(500)$ and $T(100)=100C\log(100)$. Then $100C=\dfrac{T(100)}{\log(100)}$.

You get that $$T(500)=5 (100C) \log(500) = 5 \dfrac{\log(500)}{\log(100)}T(100)\approx 5 \cdot 1.35 \cdot T(100) = 6.75 \cdot T(100) = 3.4 \textrm{ms}$$

For the other complexities the computations are easier:

• quadratic: $T(n) = C n^2$ gives $$\dfrac{T(500)}{T(100)}=\dfrac{(500^2)}{100^2}=5^2=25$$ Then $T(500)=25 \cdot 0.5 = 12.5 \textrm{ms}$

• cubic: $T(n) = C n^3$ gives $$\dfrac{T(500)}{T(100)}=\dfrac{(500^3)}{100^3}=5^3=125$$ Then $T(500)=125 \cdot 0.5 = 62.5 \textrm{ms}$

Of course these values are only approximations and only give a rough idea of the running time you can expect.

Answer 2

(Too long for a comment.) The answer posted already is likely what the problem asks for, yet it may be worth noting that the question itself is ill defined, because the asymptotic behavior does not dictate what happens for small numbers like $100$ or $500\,$.

The reason why polynomial behaviors can be estimated with some confidence is that the result depends only on the ratio of the input sizes. If the input grows $5$ times larger, then the time will grow $5^1, 5^2, 5^3$ larger for linear, quadratic and cubic behaviors, respectively.

In contrast, if the input $N$ grows $5$ times larger with $\mathcal{O}(N \log N)$ behavior, then the time will grow by $\,5 \cdot \log(5N) / \log(N) = 5 \cdot\left(1 + \log(5) / \log(N)\right)\,$ which is a function that depends on $N\,$. Consider for example that the input of $100$ is a weight measured in grams ($\text{g}$). Then the time to process $500\,\text{g}$ would calculate to $\,0.5 \cdot 5 \cdot \log(500) / \log(100) \simeq \color{red}{3.37 \,\text{ms}}\,$. However, the same weight measured in kilograms ($\text{kg}$) is $100\,\text{g} = 0.1\,\text{kg}\,$, and the time to process $500\,\text{g} = 0.5\,\text{kg}\,$ would come out to be $\,0.5 \cdot 5 \cdot \log(0.5) / \log(0.1) \simeq \color{red}{0.75 \,\text{ms}}\,$, instead. The two estimates are far apart, though the actual time to process a given weight would obviously be the same, regardless of whether it's measured in grams or kilograms.