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
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) = ?
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.
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)
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).
how to calculate time complexity of various decision tree algorithms?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.