Wednesday, May 4, 2016

what is the Complexity of Bubble Sort?

Complexity of Bubble Sort : The time for a sorting algorithm is measured in terms of the number of comparisons. The number f(n) of comparisons in the bubble sort is easily computed.Specially, there are n - 1 comparisons during the first pass, which places the largest element in the last position; there are n - 2 comparisons in the second step, which places the second largest element in the next-to-last position; and so on.  Thus

f(n) = (n-1) + (n-2) + .......... + 2+1 = n(n-1)/2 - n2/2 +0(n) = 0(n2)

In the other words, the time required to execute the bubble sort algorithm is propositional to n2 where n is the number of input items.


If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE


Post a Comment

Google+ Followers