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

| cite | improve this answer | |
$\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.