Bubble Sort: Runtime complexity analysis line by line I'm trying to analyze Bubble Sort runtime in a method similar to how to it's done in &quot;Introduction to Algorithms 3rd Ed&quot; (Cormen, Leiserson, Rivest, Stein) for Insertion Sort (shown below).  I haven't found a line by line analysis like the Intro to Algorithms line by line 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 &quot;optimized bubble&quot; 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$
The runtime in the original post is correct.  The O(n) runtime is for a different algorithm, called optimized bubble sort.