caculate Time complexity And Big Oh

[AlvinLiu]

int[] list;
int n, value;

input n;
list = new int[n];
for (int i = 0; i < n; i++) {
  input value;
  list[i] = value;
}

int m = 0;
for (int i = 0; i < n; i++) {
  for (int j = i+1, j < n; j++) {
    int d = Math.abs(list[j] - list[i]);
    if (m > d)
      m = d;
  }
}
output m;

please provide some details,Thanks very much

[mrnutty]

How about you give it a try and we'll be here to guide you.

[AlvinLiu]

The first loop is going from 0 to n with inrement of 1,which makes it O(n) = O(n).
Two loop nested,the first loop goes to n with increment of 1,second loop going to n,
so the complexity would be O(n + n^2).

the first loop : T(n) = n.
the second loop: T(n) = ?

[apines]

Have you read this by any chance? :)

[AlvinLiu]

yea.So my answer is right or not?
thanks

[apines]

If you want a more complete answer - the inner loop is going the first time n-1 iterations, second time n-1, third n-2, and so - we get [TEX](n-1)+(n-2)+...2+1=\frac{n*(n-1)}{2}=O(n^2)[/TEX]. Other than that you are correct.

[AlvinLiu]

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

this is my answer:
the first loop is T(n) = n
the outter loop : T(n) = n.
the inner loop run the first time is n-1,the second time is n-2,the third time is n-3,so (n-1)+(n-2)+(n-3)+...+2+1 = (n*(n-1))/2)
So T(n) = n + n*(n*(n-1))/2) = (n^3 - n^2 +2n) / 2
O(n) = O(n + n*n^2) = O(n+n^3)

[apines]

The first loop is O(n), agreed. The nested loops: The outer loop is going from 0 to n-1, meaning n iterations. The first iteration, where i=0, j will iterate from i+1=1 to n-1, meaning n-2 iteration. The second outer loop iteration, j will iterate from i+1=2 to n-1, meaning n-3 iterations. When i=n-2, j=i+1=n-2+1=n-1, meaning it will iterate precisely once. This will give us (n-1)+(n-2)+...+2+1=\frac{n*(n-1)}{2} = O(n^2). You don't need to multiply by n since you have already counted the outer loop iterations with the sum. Think about it like this, if you had the code

for (int i = 0; i < n; i++) {
  for (int j = 0, j < n; j++) {
    int d = Math.abs(list[j] - list[i]);
    if (m > d)
      m = d;
  }
}

The result will be O(n^2) right? The calculation would have been similar only n+n+n+...+n=n*n=n^2=O(n^2). So it can't be that when the inner loop is doing less iterations, it will have bigger complexity. Besides - you have two loops with O(1) operations inside, it cannot be bigger than O(n^2).

[gnanasemantic]

how to calculate time complexity of various decision tree algorithms?