# Bubble Sort: Runtime complexity analysis like Cormen does

I’m trying to analyze Bubble Sort runtime in a method similar to how Cormen does in "Introduction to Algorithms 3rd Ed" for Insertion Sort (shown below). I haven’t found a line by line analysis like Cormen’s analysis of this algorithm online, but only multiplied summations of the outer and inner loops.

For each line of bubblesort(A), I have created the following times run. Appreciate any guidance if this analysis is correct or incorrect. If incorrect, how it should be analyzed. Also, I do not see the best case where $$T(n) = n$$ as it appears the inner loop always runs completely. Maybe this is for "optimized bubble" sort, which is not shown here?

Times for each line with constant run time $$c_n$$, where $$n$$ is the line number:

Line 1: $$c_1 n$$

Line 2: $$c_2 \sum_{j=2}^n j$$

Line 3: $$c_3 \sum_{j=2}^n j – 1$$

Line 4: $$c_4 \sum_{j=2}^n j – 1$$ Worst Case

$$T(n) = c_1 n + c_2 (n(n+1)/2 – 1) + c_3 (n(n-1)/2) + c_4 (n(n-1)/2)$$

$$T(n) = c_1 n + c_2 (n^2/2) + c_2 (n/2) – c2 + c_3 (n^2/2) – c_3 (n/2) + c_4 (n^2/2) – c_4 (n/2)$$

$$T(n) = (c_2/2+c_3/2+c_4/2) n^2 + (c_1 + c_2/2+c_3/2+c_4/2) n – c_2$$

$$T(n) = an^2 + bn – c$$  Posted on Categories proxies