For the bubble sort with N items to sort, show that the number of iterations req

Question

For the bubble sort with N items to sort, show that the number of iterations required to complete the sort is given by the following attached (you can do this by showing a couple of example N values and extrapolating from there):

(N-1 (sum notation) k=1) k = ((N-1) * N) / 2

For, example, if N = 10, the number of iterations would be 9*10/2 = 45. The sigma notation, represents a sum over k. That is, for the expression in the sum (k in this case), you do a running sum for this expression over the integer values of k from 1 to N-1. I.e., 1+2+…+(N-1).

Explanation / Answer

Solution:

The pseudocode for bubble sort is

so the effective running will go as

0 1 2 3 4 .....n-1

so adding these iterations we will get

(n-1)(n+(n-1))/2 = (n-1)(n))/2, hence proved

and the time complexity will be O(n^2)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects