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$
