## 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$$

## Where can I get step-by-step solutions to Algorithms by Cormen for self study?

I want to study Algorithms myself. So, I am using Intro to Algorithms by Cormen. Where can I get reliable step-by-step solutions to all the problems in the book ?

I have seen the official Instructor solution manual and also the one by Rutgers University. Unfortunately, they are not really step-by-step. They just give you the final answer or last few steps. Ex. in the insertion sort example, the exact steps to figure out the equation for running time are provided. But, in the exercise for selection sort, only the final equation is given.

Thanks !

PS – Please let me know if there is a better forum to ask this instead of this one.