BIG O

[jGAShbRD]

You have the following piece of code:

for(int i{0}; i<SIZE; i++)

for(int j{0}; j<i; j++)

sum*=matrix[i][j];



A) How many multiplications will happen when SIZE=3 ? i know the answer is 3 but y is it 3 and not 6? isnt it n(n-1) ? like when j<size for size 3 the answer is n*n = 9

B) How many multiplications will happen when SIZE=6 ? i know the answer is 15 but why

[malibor]

For both A) and B) the answer is the same, that is:
O(a * r ^ (n - 1))

Where, a is the first loop whose value is n = 1, and r is common ratio, and n is number of loops.

I think geometric progression is the answer, but I could be wrong.

[Ganado]

For (A), the first inner loop won't run, because j = i = 0, and j is not < i.
If it were "j <= i", then you'd get 6 inner loop runs that you seem to expect.

(B) Honestly, if you're not sure, then just start counting it. You'll notice a pattern sooner or later.

The following modification to your program might make the pattern easier to see.

#include <iostream>
int main()
{
    const int SIZE = 6; // change this to test
    for(int i{0}; i<SIZE; i++)
    {
        for(int j{0}; j < i; j++)
        {
            std::cout << ".";
        }
        std::cout << "\n";
    }
}

.
..
...
....
.....

padding out to a 6x5 rectangle:

xxxxx
.xxxx
..xxx
...xx
....x
.....

You'll see that the x's are symmetric to the dots, and since the area of the rectangle is (n)(n-1), the number of dots must be half that, or (n)(n-1)/2.

In other words, for a given size of n, the number of dots is the (n-1)th triangular number in your code.
Given T(n) = (n)(n+1)/2, it means T(n-1) = (n-1)(n)/2.

https://en.wikipedia.org/wiki/Triangular_number
SIZE = 6 ---> produces 5th triangle number --> (5)(6)/2 = 15.

[jonnin]

and, (n-1)*n/2 is just O(n*n), following Ganado's thinking but you need to make sure we are not playing fast and loose with what 'n' is. Going with malibor's thought that a is related to N, the big-o answer is just n squared. Messing up what n means in the middle of analysis is the #1 cause of messed up answer ... start out counting how many comparisons you are doing and then forget and halfway thru start counting only the swaps... etc... oops :)

[malibor]

Going with malibor's thought that a is related to N, the big-o answer is just n squared.

My mistake, I should have told that a must be exactly 1 (in order for loop to reach inner loop), but is otherwise unrelated to n, which is total loop of inner loop.

This means big o can't be a square which would assume arithmetic progression.

My idea is based on geometric progression which means increments are done by multiplying previous result with common ratio:
https://en.wikipedia.org/wiki/Geometric_progression