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

4
Contributors
8
Replies
9
Views
7 Years
Discussion Span
Last Post by gnanasemantic

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

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) = ?

Have you read this by any chance? :)

yea.So my answer is right or not?
thanks

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.

Edited by apines: n/a

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

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)

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).

Edited by apines: n/a

how to calculate time complexity of various decision tree algorithms?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.