CODEWITHSUNDEEP
algorithmsortingbig-obubble-sort
gython
gython

Reputation: 875

How does the time complexity of the bubble sort algorithm result in O(n^2) regarding the way you calculate it?

I understand that why bubble sort is O(n^2).

However in many explanations I see something like this:

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2

How do you calcuate Sum from this part:

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

Can anyone help?

Upvotes: 2

Views: 570

Answers (2)

Spektre
Spektre

Reputation: 51845

The simplest "proof" to understand without deriving the equation is to imagine the complexity as area:

so if we have sequence:

n+(n-1)+(n-2)...

we can create a shape from it... let consider n=5:

n     5     *****
n-1   4     ****
n-2   3     ***
n-3   2     **
n-4   1     *

Now when you look at the starts they form a right angle triangle with 2 equal length sides ... that is half of n x n square so the area is:

area = ~ n.n / 2 = (n^2)/2

In complexities the constants are meaningless so the complexity would be:

O(n^2)

Upvotes: 2

Patrick87
Patrick87

Reputation: 28302

Here's the trick:

If n is even:
  n + (n-1) + (n-2) + … + 3 + 2 + 1
= [n + 1] + [(n-1) + 2] + [(n-2) + 3] + … + [(n - (n/2 - 1)) + n/2]
= (n + 1) + (n + 1) + (n + 1) + … + (n + 1)
= n(n+1)/2

If n is odd:
  n + (n-1) + (n-2) + … + 3 + 2 + 1
= [n + 1] + [(n-1) + 2] + [(n-2) + 3] + … + [(n - (n-1)/2 + 1) + (n-1)/2] + (n-1)/2 + 1
= (n+1) + (n+1) + (n+1) + … + (n+1) + (n-1)/2 + 1
= (n+1)(n-1)/2 + (n-1)/2 + 1
= (n^2 - 1 + n - 1 + 2)/2
= (n^2 + n)/2
= n(n+1)/2

For your case, since you're counting up to n-1 rather than n, replace n with (n-1) in this formula, and simplify:

   x(x+1)/2, x = (n-1)
=> (n-1)((n-1)+1)/2 
 = (n-1)(n)/2 
 = n(n-1)/2

Upvotes: 2

Related Questions