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 an algorithm and I would like to know how many times each line is called. There I wrote which lines I understand and some lines is left.

j := 1   ---------------------- 1 time
while j < n do  --------------- n times
  x := B[j]    ---------------- n-1 times
  k := j    ------------------- n-1 times
  for i := j + 1 to n do  ----- ?
    if B[i] < x then     ------ ?
      x := B[i]     ----------- ?
      k := i    --------------- ?
  B[l] := B[j]   -------------- n-1 times
  B[j] := x     --------------- n-1 times
  j := j + 1   ---------------- n-1 times

Note: k := i means that line is called once but for i := j + 1 to n do - twice: assign and comparison.

share|improve this question
add comment

2 Answers

Since B[i] can change depending on some as yet unknown thing (maybe some values of B[1], B[2], B[3],.. will behave differently than others, at this point e don't know maybe it will maybe it won't), let's start off by simplifying, getting rid of the stuff we don't know about and leaving unconditional operations:

j := 1   ---------------------- 1 time
while j < n do  --------------- n times
  k := j    ------------------- n-1 times
  for i := j + 1 to n do  ----- ?
    k := i    ----------------- ?
  j := j + 1   ---------------- n-1 times

(This is the point of worst-case analysis, because of the conditional and the data in B, things may go much faster, but at least it'll be no worse than the analysis we're about to do.

The inner loop will occur altogether $n-1$ times (think of it just like the other assignments). But each operation in that inner loop (incrementing the $i$, comparing it to $n$, setting $k$ to $i$) how many times will they take place? Well, from $j+1$ to $n$ times. Which is $n - j - 1$. So as $j$ goes from 1 to $n$, $i$ goes from $j+1$ to $n$. This can be expressed as a summation: $$\sum^n_{j=1} \ \sum^n_{i=j+1} ???$$ What is the question mark? What is the inner thing being summed? Well, let's be simple, ignore the extra comparisons and additions in the 'for' command' and just count the 'k := i ' assignment or 1 operation. So the summation looks like this: $$\sum^n_{j=1} \ \sum^n_{i=j+1} 1.$$ Now you should be able to find it easier to manipulate this sum than it is to manipulate the programming language operations. For example, summing 1 from $a$ to $b$ is the same as summing 1 from 0 to $b-a$ which is equal to $b-a+1$ (why the '$+1$'?).

Once you can manipulate the summation, then you can go back to adding in complexities, like multiple assignments. You'll realize that those simplifications I made were not really important,they only change a constant in front of the final answer.

Since for this algorithm (insertion sort), it ends up being dependent on the actual data $B$ being sorted, the worst case is the most exact answer you'll get (you really don't want to worry about the conditional) unless you know something about what $B$ looks like (is it already sorted, in reverse, some interesting subset of permutations, etc.

share|improve this answer
add comment

Hint: You enter the for loop n-1 times as shown from the line above. Then how many loops to you do? It should be something like n-j, but you have to figure out the ends-there may be a +1 or -1 or something. Does your definition of for do the loop with i=n or not? so the for will be executed 2*(n-1)*(something like n-j) times. Given the if statement, you can't say for sure how many times the lines within it are executed. All you can do is find a maximum, assuming the if always evaluates as true.

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