Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
    
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
show 2 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.