CODEWITHSUNDEEP
asymptotic-complexity
user1189352
user1189352

Reputation: 3885

Calculating Time Complexity.. Need help coming up with the end result

Studying for a midterm tomorrow, and these time complexities are something I struggle with. I'm going over the simple examples in the book and for this example

Exchange Sort

void exchangesort (int n, keytype S[])
{
  index i, j;
  for(i=1; i<=n-1; i++)
    for(j=i+1; j<=n; j++)
      if(S[j] < S[i])
        exchange S[i] and S[j];
}

For the "Every-Case Time Complexity" of this Exchange sort, I understand the part that we pretty much analyze the j for-loop, because it has the basic operation (the exchange). And so if you list out the total number of passes, it's given by:

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

Now my question is... where does the 1 come from? I thought it was n-1 + n-2 +... + n.

Furthermore, what I really don't understand is how to come up with the (n-1)n/2.
That's obviously what I have to come up with in the midterm, and by looking at that, (n-1)n/2 doesn't come intuitively... I understand how to come up with the T(n) = (n-1) + (n-2) etc., I think...

Can someone explain this to me in laymen's terms so I can come up with an answer like this for my midterm tomorrow?

Upvotes: 0

Views: 145

Answers (4)

Daniel Fischer
Daniel Fischer

Reputation: 183888

In the inner loop, j runs from i+1 to n, that is, through n-i values. So altogether, there are

sum_{i = 1 to n-1} (n-i)

steps, (n-1) + (n-2) + ... + (n - (n-1)) = (n-1) + (n-2) + ... . 1.

Now, for the sum of the first k positive integers, there is a closed formula, it's

k*(k+1)/2

Here, k = n-1.

To work out the formula for the sum of the first k positive integers, there are several nice ways, as mentioned in robert king's answer. Allegedly, Gauss worked it out in the first way when he was five years old and the teacher gave the pupils the task to calculate the sum of the integers from 1 to 100 in the hope of having a few quiet minutes. It's better to see if arranged thus:

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

Upvotes: 4

Rusty Rob
Rusty Rob

Reputation: 17173

one way of working it out is:

sum=1+2+3+4+...+n

2*sum = 1+2+3+4+...+n + 1 + 2 + 3 + 4 +...+n = 1+(n) + 2+(n-1) + 3+(n-2)..+ (n)+1

2*sum=1+n + 1+n + 1+n...

2*sum = n(1+n)

sum=n*(n+1)/2

but an easier way to see this is to imagine a square or a grid matrix.

as i goes down to each new row, j goes across and extra column to the diagonal of the matrix (as i<=j .. we know j can't get past the diagonal). This means all the operations are a combination of (i,j) on one side of the matrix's diagonal. The number of operations is therefore half the area of the entire matrix. if the matrix is a n*n matrix, then we have about n*n/2 area (but since we can't count the diagonal twice its actually n*(n-1)/2

Upvotes: 1

noMAD
noMAD

Reputation: 7844

The series goes from (n-1) to (1) [(n-1), (n-2) ... (n-(n-1))] check the sum of the series here to know how it was derived. Its pretty easy to understand.

Upvotes: 0

Sufian Latif
Sufian Latif

Reputation: 13356

OK, think like this:

When i = 1, inner loop runs (n - 1) times [j = 2 to n]
When i = 2, inner loop runs (n - 2) times [j = 3 to n]
When i = 3, inner loop runs (n - 3) times [j = 4 to n]
....
When i = k, inner loop runs (n - k) times [j = k + 1 to n]
...
When i = n - 1, inner loop runs (n - (n - 1)) = 1 time [j = n to n]

Now sum them up:

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

In the worst case, the exchange will be done n(n - 1) / 2 times.

Upvotes: 0

Related Questions