Nested for loop summation

Question

Func(V, n) {
   int a = 0
   int b = n - 1

   while(a < b) {
       for(int i = a; i < b; a++) { // do something }
       a = a + 1
       b = b - 1
   }
}

I want to write both the while loop and the for loop using the sigma notation. The only problem is because one variable is increasing and the other one is decreasing. The way I approached this problem was by writing $\Sigma_{k = 1}^{n/2} 1$ and therefore I conclude that it runs $n$/2 comparisons, which is true when it comes to the while. The for loop: $\Sigma_{k = 1}^{n / 2} \Sigma_{i = k}^{n - k} 1$, I'm only counting the comparisons here. Does it make sense?

Answer 1

We start with the inner $\mathtt{for}$ loop. We can write this loop as \begin{align*} \sum_{i=a}^{b-1}f(i) \end{align*} Here we use $f(i)$ to represent the do something. The $\mathtt{while}$ loop can be written in a first step as \begin{align*} \sum_{i=a}^{b-1}f(i)+\sum_{i=a+1}^{b-2}f(i)+\cdots+\sum_{i=a+K}^{b-1-K}f(i)\tag{1} \end{align*} We determine $K$ \begin{align*} a+K&=b-1-K\\ K&=\frac{b-a-1}{2}\tag{2} \end{align*} and obtain from (1) and (2) \begin{align*} \sum_{i=a}^{b-1}f(i)+\sum_{i=a+1}^{b-2}f(i)+\cdots +\sum_{i=a+\left\lfloor\frac{b-a-1}{2}\right\rfloor}^{b-1-\left\lfloor\frac{b-a-1}{2}\right\rfloor}f(i)\\ \end{align*} which can be written as double sum \begin{align*} \color{blue}{\sum_{k=0}^{\left\lfloor\frac{b-a-1}{2}\right\rfloor}\sum_{i=a+k}^{b-1-k}f(i)} \end{align*}