After doing some research on Bubblesort I found that there are 2 relevant measures for speed comparing, the average number of comparisions and the average number of exchanges. Average number of comparisions is: 1/2*(n^2-n*log(n)) = O(n^2) Average number of exchanges is: 1/4*n*(n-1) = O(n^2) However I have no idea how these formulas can be found out. Can somebody try and explain this to me or point me to some link or something?? Thank You

In this case its relatively easy to figure it out. Basically you''re trying to find the worst case and figure out how many iterations must be undertaken to perform the operation.

The worst case for a bubble sort would be that an element at the end of a list, containing n elements, must be sorted to the front of the list. In a bubble sort, we have a bubble that rises through the list and swaps around 2 adjacent elements at a time as it moves up if they are out of order. In one pass of the bubble through a list, an element can only move 1 position in the correct direction.

Now, if we have to move the element at the end of the list to the start of the list this means that we will have to go up through the list ''n'' times (ie make ''n'' passes), as the element must move ''n'' places down the list and we can only move it one place down per pass of the list.

Because we don''t have any exact numbers in this, we''re just looking for an approximation of the worst case time so we can compare the relative expected performance difference for different numbers of elements, we chuck out terms that are insignificant:
-For large n, n*log(n) tends to n, and in comparison to n^2, n is insignificant.
-again, for large n, (n-1) is close to n, so it is taken as ''n''
-The coefficients (1/2 & 1/4) disappear as they are irrelevent in the context of relative time for different ''n'' values.

Does that help make things clearer ? Hope it helps....

First of all thank you ap, well I sort of begin to understand what''s going on.
Can the left side (and where the different parts came from) be explained as well to me from somebody please?
I now see the whole O(n^2) stuff, but I have no idea where the other stuff is from or how log(n) plays any role in bubblesort etc.
thx

This is called Order of Complexity. It is used to measure an algorithm''s complexity. If you come with an algorithm to do something you can sit down and figure out how complex it is before you even implement it, which could tell you whether or not you even should implement it.
Here''s a link you can check out for more info.
http://cs-netlab-01.lynchburg.edu/courses/DiscMath/Stud18.htm