# 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 "Introduction to Algorithms 3rd Ed" (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 "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$$

• Introduction to Algorithms has four authors. The one you mention is the lexicographically first one. Aug 20, 2020 at 8:29
• Updated to reflect this
– Nick
Aug 20, 2020 at 16:52
• Your analysis seems to be correct. Also the best case runtime of $O(n)$ only applies for optimized bubble-sort and not to the one you are given. Wikipedia explains the "optimized" version en.wikipedia.org/wiki/Bubble_sort Aug 23, 2020 at 0:28