Calculating the time complexity of Bubble sort

Question

Question

I am interested in finding the time complexity of Bubble sort by simplifying the summation.

My Approach

$$\sum _{i=0}^{i=n-1}\,\,\sum _{j=0}^{j=n-i-1}1\text{(some constant)}=\sum _{i=0}^{i=n-1} n-i$$ $$\sum _{i=0}^{i=n-1} n-\sum _{i=0}^{i=n-1}i=n^{2}-\frac{n (n-1)}{2}$$

$$=\frac{n (n+1)}{2}$$ i.e $O(n^{2})$

Am i correct? Can i say that #of comparison in bubble sort will be $$=\frac{n (n+1)}{2}$$

Answer 1

Your calculations are correct (and consequently, so are you), but you should be able to avoid the worst-case scenario.

For example, pre-compute the number of unrespected order in a first run and choose to go in the other direction if it's bigger than half the size of your list. Intuitively, this would yield a $\frac{n^2}{4}$ complexity.