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;

Bulbous

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. – Programme

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. – Perfectible

I don't see why you ask for "worst case" time complexity, because there are no cases here -- it always does the same operations. – Cathepsin

Answer 1

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?

Programme

Why sum them in the same loop? – Cathepsin

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. – Programme

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

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. – Cathepsin

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

Answer 2

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

1. https://mcmap.net/q/269984/-what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop-is-determined-by-the-current-iteration-of-the-outer-loop
2. https://mcmap.net/q/271060/-time-complexity-of-nested-for-loop
3. https://mcmap.net/q/271062/-o-n-and-time-complexity-function-of-the-given-code
4. https://mcmap.net/q/271063/-using-big-o-notation-what-is-the-correct-label-for-this-algorithm
5. https://mcmap.net/q/271064/-nested-for-loop-in-big-oh-complexity

Whilom

Answer 3

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.

Dyson

Answer 4

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

Guenna