CODEWITHSUNDEEP
c++algorithmtime-complexity
user2809437
user2809437

Reputation: 492

theoretical analysis of multiplications in function

Do a theoretical analysis for the running time of the following C++ function MMultiply. Count the number of multiplications MMultiply does as a function of n because in this case, n is the size of the input/size of the problem. Show your workings. Express the answer in big O notation. 

int I(int i, int j, int n)
{
    return n * i + j;
}

int sProduct(const int A[],const int B[],int i, int j, int n)
{
    int t = 0;
    for( int k=0; k<n; k++ )
    {
        int d = A[ I(i,k,n) ] * B[ I(k,j,n) ];
        t += d * d;
    }
    return t;
}

void MMultiply(const int A[], const int B[], int C[], int n)
{
    for( int i=0; i<n; i++ )
        for( int j=0; j<n; j++ )
            C[ I(i,j,n) ] = sProduct(A, B, i, j, n );
}

Answer was found to be O(n^3), but I dont understand how this was computed.

The outer loop in MMultiply gives n, the inner loop is n, so then looking at the functions with multiplication there are 3......M(n)=n*n(....) then I'm lost on how to look at the other functions.The T(n) and C(n) notations are also throwing me off...

Upvotes: 1

Views: 208

Answers (1)

Adam
Adam

Reputation: 17379

  • i goes from 0 to n, so n times in total.
  • for each i, j goes from 0 to n, so n times for each i, n*n times in total.
  • for each j, k goes from 0 to n, so n times for each j, n*n*n times in total.

The lines that do work, i.e.:

int d = A[ I(i,k,n) ] * B[ I(k,j,n) ];
t += d * d;

get executed n*n*n = O(n3) times.

There is another line that does work. The assignment here:

C[ I(i,j,n) ] = sProduct(A, B, i, j, n );

gets executed n*n = O(n2) times. So the entire algorithm is O(n3 + n2). As n grows the n2 term is insignificant, so the entire algorithm is O(n3).

That gives us the upper bound, i.e. what happens in the worst case. Note that even in the best case those lines still get executed n3 times, so you can say that the lower bound is Ω(n3) as well. That means that the algorithm is Θ(n3) (i.e. lower and upper bounds are the same).

Upvotes: 3

Related Questions