procedure matrixvector(n:integer);
var i,j:integer;
begin
for i<-1 to n do begin
B[i] = 0;
C[i] = 0;
for j<-1 to i do
B[i]<- B[i]+ A[i,j];
for j<-n down to i+1 do
C[i]<-C[i] + A[i,j]
end
end;
views:
1151answers:
5
+8
A:
O(n^2), if I read it right.
Why you need two inner loops is beyond me. Why not sum B and C in the same loop?
duffymo
2009-01-09 13:42:38
Why sum them in the same loop?
ShreevatsaR
2009-01-09 13:55:19
Why not? DRY principle says you'll have one less loop. What advantage is there to having individual sums like this? n*(n+n) = 2n^2 for two loops; n*n = n^2 for one. Big-O leaves off constants, but your wall clock doesn't.
duffymo
2009-01-09 14:43:49
but the inner loop sizes aren't n, they sum to n, so this should have approximately the same running time as if the loops were combined. actually, it might be faster because if the loops were combined you'd need to switch or if based on the value of the loop index (B if j < i else C).
Autoplectic
2009-01-09 17:17:03
Yeah, exactly what Autopletic says. Whether you "combine" them or have them separate, you'll perform the same additions, and the loops run the same number of times -- and trying to do both in the same loop only makes it messier with the "if j<=i add A[i,j] to B[i] else add it to C[i]" test.
ShreevatsaR
2009-01-09 18:38:45
My wall clock shows that it's faster to use two inner loops than one. (Which is what you would expect from the code, anyway).
ShreevatsaR
2009-01-11 15:55:53
A:
I agree with duffymo on the complexity, but the two loops are needed to do that kind of adding. It wouldn't change anything about the complexity, if it was written somehow differently.
DaDaDom
2009-01-09 13:51:21
+1
A:
worst case is O(n²).
there are indeed three loops, but not all inside each other, thus giving O(n²).
also, you can clearly see that the inner loops won't go from 1 to n (like the outer loop does). But because this would only change the time complexity by some constant, we can ignore this and say that it is just O(n^2).
This shows that time complexity is a measure saying: your algorithm will scale with this order, and it won't ever take any longer. (faster is however always possible)
for more information about "calculating" the worst case complexity of any algorithm, I can point you to a related question I asked earlier
Sven
2009-01-09 13:52:22
A:
"needed"? Why not sum both inside one loop? It's not necessary to break them out.
duffymo
2009-01-09 14:45:18