[Math] Simple Algorithm Running Time Analysis

algorithmsanalysis-of-algorithms

A sorting algorithm takes $1$ second to sort $1,000$ items on your local machine. How long will it take to sort $10,000$ items

if you believe that the algorithm takes time proportional to $n^2$,
and

if you believe that the algorithm takes time roughly proportional to
$n\log n$?

If the algorithm takes time proportional to $n^2$, then $1,000^2=1,000,000$, and $10,000^2=100,000,000$. Dividing the latter by the former yields $100$. Therefore, the sorting algorithm would take $1$ minute and $40$ seconds to sort $10,000$ items.

If the algorithm takes time proportional to $n\log n$, then $1,000\log 1,000=3,000$, and $10,000\log 10,000=40,000$. Dividing the latter by the former yields $13\frac13$. Therefore, the sorting algorithm would take $13.\bar3$ seconds to sort $10,000$ items.

Does my thought process seem correct?

Best Answer

Yes, it seems correct. -Servaes

Related Solutions

[Math] Computer Algorithm Running Time Calculation

I don't know if another answer can be more illuminating to you, but let me try saying it a bit differently anyway.

First, consider the inner loop:

    for k= 1 to m
        //dowork  ---- CONSTANT

Because it's doing a constant amount of work $m$ times (for k=1 to m), this takes approximately time $m$, whatever the value of $m$ is. (To be precise, it takes $\Theta(m)$ time, which means that there are constants $c_1$ and $c_2$ such that the time it takes is between $c_1m$ and $c_2m$, but when finding the "approximate running time", i.e., the asymptotic complexity, we usually ignore constant factors.)

Now the outer loop looks like

m = n
while (m > 0)
      //Do 'm' amount of work
      m = floor(m/2)

where I've replaced the inner loop with what we know about its time. So the first time the loop is run, $m=n$ and it takes time $n$. By the second time the loop is run, $m$ is halved, so $m = n/2$ and it takes time $n/2$ (I'm ignoring writing $\lfloor n/2 \rfloor$, because that's within a constant factor of $n/2$.) The third time it takes $n/4$, etc. So the total time taken by the code is: $$\begin{align}&n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \dots \\ &= n\left(1 + \frac12 + \frac14 + \frac18 + \dots\right)\end{align}$$ until the term becomes less than $1$ (so $m$ would have become $0$ and the code would have halted).

Now, the sum $\left(1 + \frac12 + \frac14 + \frac18 + \dots\right)$ is at most $2$, so the above sum for the running time is at most $2n$. Ignoring constant factors, we can say that the code takes approximately time $n$, which is shorthand for saying that the time it takes is is linear in $n$. Or, if we did the whole thing formally, we would have said it takes time $\Theta(n)$.

(As it happens, we can analyse the number of terms in the sum: if the last term is $\frac{n}{2^k}$ (each term is of this type), then $k$ is such that $2^k \le n < 2^{k+1}$, which means $k = \lfloor \lg n \rfloor$, but all this is irrelevant to the actual problem here.)

[Math] How long time will it take to sort $10^6$ numbers and $10^9$ numbers for two algorithms if they take the same time to sort $1000$ numbers

As it is stated, the answer is "we don't know". It follows from the $O(\cdot)$ notation — roughly speaking, you don't have enough information to infer anything. You only know the asymptotic behavior, and not even the constants.

Algorithm 1 might very well be as fast as Algorithm 2 as long as $n$ is less than, say, $10^{10}$, and then break down.

Even worse, the big-Oh notation is only an upper bound. For all we known, both could have the same running time $O(n\log n)$, since if Algorithm 1 had running time $O(n\log n)$, it would also trivially have running time $O(n^2)$.

Best Answer

Related Solutions

[Math] Computer Algorithm Running Time Calculation

[Math] How long time will it take to sort $10^6$ numbers and $10^9$ numbers for two algorithms if they take the same time to sort $1000$ numbers

Related Question