What is the worst case time complexity for this algorithm?

Question

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;

I thought my eyes were tricking me. When I first read this it wasn't formatted. When the page refreshed, it was nicely formatted and Jon Skeet's picture was in front of me. — duffymo, Jan 09 '09 at 13:44
I think the format is part of the trick here. I couldn't see it's two loops inside another loop the first time, and thought there are 3 nested loops. — PolyThinker, Jan 09 '09 at 13:48
I don't see why you ask for "worst case" time complexity, because there are no cases here -- it always does the same operations. — ShreevatsaR, Jan 11 '09 at 15:44

score 9 · Answer 1 · answered Jan 09 '09 at 13:42

9

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?

answered Jan 09 '09 at 13:42

duffymo

305,152
44
369
561

Why sum them in the same loop? – ShreevatsaR Jan 09 '09 at 13:55
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 Jan 09 '09 at 14:43
2

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 Jan 09 '09 at 17:17
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 Jan 09 '09 at 18:38
1

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 Jan 11 '09 at 15:55

Deepthi Tabitha Bennet · Answer 2 · 2022-04-28T16:05:50.903

Let us trace the number of times each loop executes in each iteration.

procedure matrixvector(n : integer);
var i, j : integer;
begin
    for i<-1 to n do begin   // OuterLoop
        B[i] = 0;
        C[i] = 0;

        for j <- 1 to i do   // InnerLoop_1
            B[i] <- B[i] + A[i, j];

        for j <- n down to (i + 1) do   // InnerLoop_2
            C[i] <- C[i] + A[i, j]
    end
end;

`InnerLoop_1`

In the first iteration of OuterLoop (i = 1), InnerLoop_1 executes once.

In the second iteration of OuterLoop (i = 2), InnerLoop_1 executes twice.

In the third iteration of OuterLoop (i = 3), InnerLoop_1 executes thrice.

. . .

In the last iteration of OuterLoop (i = n), InnerLoop_1 executes n times.

Therefore, the total number of times this code executes is

1 + 2 + 3 + … + n

= (n(n + 1) / 2) (Sum of Natural Numbers Formula)

= (((n^2) + n) / 2)

= O(n^2)

`InnerLoop_2`

In the first iteration of OuterLoop (i = 1), InnerLoop_2 executes n - 1 times.

In the second iteration of OuterLoop (i = 2), InnerLoop_2 executes n - 2 times.

In the third iteration of OuterLoop (i = 3), InnerLoop_2 executes n - 3 times.

. . .

In the n - 2th iteration of OuterLoop (i = n - 2), InnerLoop_2 executes 2 times.

In the n - 1th iteration of OuterLoop (i = n - 1), InnerLoop_2 executes 1 time.

In the last (nth) iteration of OuterLoop (i = n), InnerLoop_2 executes 0 times.

Therefore, the total number of times this code executes is

n - 1 + n - 2 + n - 3 + … + 2 + 1 + 0

= 0 + 1 + 2 + … + n - 3 + n - 2 + n - 1

= (n - 1)((n - 1) + 1) / 2 (Sum of Natural Numbers Formula)

= (n - 1)(n) / 2

= (((n^2) - n) / 2)

= O(n^2)

`Time Complexity`

Number of times InnerLoop_1 executes : (((n^2) + n) / 2)

Number of times InnerLoop_2 executes : (((n^2) - n) / 2)

Adding, we get

(((n^2) + n) / 2) + (((n^2) - n) / 2)

= ((((n^2) + n) + ((n^2) - n)) / 2)

= (((n^2) + n + (n^2) - n) / 2)

= (((n^2) + (n^2)) / 2)

= ((2(n^2)) / 2)

= (n^2)

= O(n^2)

——————

Also, do take a look at these

score 3 · Answer 3 · answered Sep 22 '17 at 02:19

Just explaining in detail for beginners:

Outermost for loop will run n times (0 to n) Then there are two for loops within the out ermost for loop. First for loop will go from 1 to n (1+2+3+4+.....+n) And the second for loop will go from n to 1 (n+n-1+n-2+....+1)

The summation formula for (1+2+3+4+5+....+n ) is n(n+1)/2

so the total running time can be computed as n + n(n+1)/2 + n(n+1)/2

Observe the highest polynomial in this equation, it is n^2.

We can further simplify this equation and drop the constants and ignore the linear part, which will give us a run time of n^2.

score 2 · Answer 4 · edited May 23 '17 at 12:11

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

What is the worst case time complexity for this algorithm?

4 Answers4

`InnerLoop_1`

`InnerLoop_2`

`Time Complexity`

Linked