# Algorithm complexity in for loop

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.

-

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.

-

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.

-