0
$\begingroup$

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$

Bubble Sort from Cormen

Insertion Sort from Cormen

$\endgroup$
3
  • 1
    $\begingroup$ Introduction to Algorithms has four authors. The one you mention is the lexicographically first one. $\endgroup$ Aug 20 '20 at 8:29
  • $\begingroup$ Updated to reflect this $\endgroup$
    – Nick
    Aug 20 '20 at 16:52
  • $\begingroup$ 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 $\endgroup$
    – plshelp
    Aug 23 '20 at 0:28
0
$\begingroup$

The runtime in the original post is correct. The O(n) runtime is for a different algorithm, called optimized bubble sort.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.