for(i=1;i<=(n-1);i++)
{
for(j=(i+1);j<=n;j++)
{
T=a[i,j];
a[i,j]=a[j,i];
a[j,i]=T;
}
}
views:
98answers:
2
+7
A:
The inner loop does decreasing work from n to 1, and the actual work being done (swapping numbers) is O(1), so:
n operations + (n - 1) operations + (n - 2) operations + ... + 2 operations + 1 operation = sum(1, n) operations = (n * (n + 1)) / 2 = (n2 + n) / 2 = O(n2)
Chris Schmich
2010-08-23 08:04:01
+1
A:
for(i=1;i<=(n-1);i++) {
for(j=(i+1);j<=n;j++) {
T=a[i,j];
a[i,j]=a[j,i];
a[j,i]=T;
}
}
The time complexity is O(n^2).
Dimitar
2010-08-23 08:04:12