# Computer Algorithm Running Time Calculation

I have the following pseudocode to figure out the approximate running time of. Anyone able to help but please explain each step and reason. thanks in advance

int m = n;

while (m > 0)
for k= 1 to m
//dowork  ---- CONSTANT
m = floor(m/2)


Another Algorithm I would appreciate a break down of please. How would I compute the running time of this algorithm?

NB. This is taken from the wiki site writeup on merge sort but since that did not help, I was wondering if someone here would help break it down so I get where the O (n log n) comes from, for both best case and worst case.

http://en.wikipedia.org/wiki/Merge_sort

A

 function merge_sort(m)
if length(m) ≤ 1
return m
var list left, right, result
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result


B

 function merge(left,right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result

-
m is not changing so why will this code ever halt. And if m >= 0 in the beginning why will while loop ever run? – Pratik Deoghare Jul 13 '11 at 23:48
m is changing, in the floor m/2 function – user10695 Jul 13 '11 at 23:51
Are you saying that m changes to $\lfloor m/2 \rfloor$? – mixedmath Jul 13 '11 at 23:55
By the way - then m will forever halt at -1 even if it does change. – mixedmath Jul 13 '11 at 23:55
@user10695 then write m = floor(m/2) in the code. – Pratik Deoghare Jul 14 '11 at 0:04

## 2 Answers

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

-
This line "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$." I am not sure exactly how you got it. I mean would it not be less than n since we are dividing n into bits? – user10695 Jul 15 '11 at 1:49
@user10695: The sum starts with "1" and then adds some more numbers, so it can't be less than 1. :-) It's the geometric series with ratio $1/2$. Or, if you don't know what that is, it may help to look at some partial sums: $1+1/2=1.5$, $1+1/2+1/4=1.75$, $1+1/2+1/4+1/8=1.875$, etc. (Each time you add only half the remaining distance to 2, so you never reach 2.) So $n(1+1/2)=1.5n$, $n(1+1/2+1/4)=1.75n$, etc. The sum $n(1+1/2+1/4+\dots)$ is at most $2n$. In $n+(n/2+n/4+\dots)$, you're adding $n$ to bits of $n$ that total at most another $n$. – ShreevatsaR Jul 15 '11 at 4:41
Ok. So how come you have it that 2n is bounded above by n? – user10695 Jul 15 '11 at 5:02
@user10695: 2n is obviously not bounded above by n; it is twice as big as n. What I said is that, ignoring constant factors (the constant factor 2), 2n is the same as n. "2n is the same as n up to constant factors": it is linear in n. Or formally, $2n=\Theta(n)$. The final conclusion, that the code takes time "approximately n", or $\Theta(n)$ to be precise, must be read as "there exist constants $c_1$ and $c_2$ so that the time it takes is between $c_1n$ and $c_2n$". (Note how I similarly ignored the constant time taken by "//dowork ---- CONSTANT" in the inner loop: took it as just 1.) – ShreevatsaR Jul 15 '11 at 5:29
Can I add a couple more algorithms for you to help me with? I mean I readlly want to understand this thing. – user10695 Jul 15 '11 at 20:35

Assuming that floor(m/2) means 'replace m with floor(m/2)' then:

Assume $n$ is a power of 2, so that $n=2^p$. You set $m = n$ in the first line. In the first line of the while loop you iterate through $k = 1...m$, which takes $am = 2^pa$ operations, where $a$ is the number of steps in your //do work block.

Then you halve $m$ - the amount of work here is nontrivial, let's call it $d$. It will almost certainly turn out to be insignificant, but...

Now you iterate through $k=1...m/2$, doing $am/2 = 2^{p-1}a$ operations, and again halve m, taking $d$ operations.

In the next pass you do $am/4 + d$ operations, in the pass after you do $am/8 + d$, until in the final pass you do $a$ operations.

You went through the while loop $p$ times, and the total amount of work you do is

\begin{align} pd + a(1 + 2 + \cdots + 2^p) & = pd + (2^{p+1}-1)a \\ & = d\log_2 n + (2n - 1)a \end{align}

If $a>d$ (likely in applications) and $a$ is independent of the loop value $k$ (may or may not be true) then the running time is linear in $n$.

-
Assume the work done within the second loop is constant, and the work done when m is halved is also constant. Would your algorithm still look the same as it does now? What I am trying to do is understand exactly why you chose to analyze it in the you have above. – user10695 Jul 14 '11 at 1:54
Yes, my answer would be the same (the line "if $a$ is independent of the loop value $k$" was where I made the assumption that the amount of work done in the second loop was constant). Rereading, although my answer is correct, I think my presentation is slightly unclear - you could learn more from ShreevatsaR's answer. – Chris Taylor Jul 14 '11 at 7:49
Definitely trying to learn from it all but I am still about 20% on doing this but would like to master it. – user10695 Jul 15 '11 at 21:45