Simple sort worst case comparisons

Question

I am working through a series of algorithm problems and determining their complexity using sum notation.

One particular sorting algorithm is quite simple but I cannot piece its worst-case # of comparisons together. I see the pattern, but I cannot grasp how it becomes a sum (or sum of sums, likely).

Pseudocode:

i = 1
while i < n
    if a[i] > a[i+1]
        i = 1
    else
        i = i + 1
    end if
end while

I wrote the algorithm up in Ruby and the number of comparisons occurring in arrays of sizes 2-7 respectively is: [1, 2, 6, 13, 24, 40]

Notably, whenever the algorithm moves left to right until it hits a new max value, i.e. the 5th element, for the first time, it must go back and compare the elements 1,2,3,4-->1,2,3-->1,2-->1 ... because it resets to index 1 every time it does a swap

I came up with: Sum(i=1, n-1) of Sum(j=i, 1) of Sum(1, j) of 1

But that doesn't seem right. Any guidance would be very much appreciated.

Answer 1

$$\sum_{i=1}^{n-1} \sum_{j=1}^i \sum_1^j1=\sum_{i=1}^{n-1} \sum_{j=1}^ij\\=\sum_{i=1}^{n-1}\frac 12(i^2+i)\\= \frac 12\left(\frac {(n-1)n(2n-1)}{6}+\frac 12(n-1)n\right)\\=\frac{n^3-n}6$$ which does not agree with your numbers. The sequence starts $0,1,4,10,20$