How to Analyze an Algorithm
Algorithm for multiplication of two matrices.
Algorithm sum(A, B, n) // A and B are square matrices of dimension nxn
Begin
For ( I= 0; I< n; I++) ; ---------------------------------n+1
{
For ( J = 0; J< n; J++) ; -----------------------------n x (n+1) =n2 +n
{
C[i, J]=0;
For ( K = 0; K< n; K++) ; -------------------------n x n x (n+1) =n3 +n2
{
C[i, J] = C[i, J] + A[I, K] x B[K, J]; -------------------------n x n x n = n3
}
}
}
Time function (or time complexity of algorithm): F(n)= 2n3 + 2n2 + 2n+1
F(n)= Θ(n3)
Analysis Piece of Code:
For ( I= n; I > 0; I--) ---------------------------------n+1 (we will ignore this)
{
Stmt; ---------------------------------n times
}
(In analysis, we consider number of times the loop body get executed, sometimes we will ignore
the number of times the loop condition get executed).
Time function (or time complexity of algorithm): F(n)= 2n +1
F(n)= Θ(n)
Algorithm for multiplication of two matrices.
Algorithm sum(A, B, n) // A and B are square matrices of dimension nxn
Begin
For ( I= 0; I< n; I++) ; ---------------------------------n+1
{
For ( J = 0; J< n; J++) ; -----------------------------n x (n+1) =n2 +n
{
C[i, J]=0;
For ( K = 0; K< n; K++) ; -------------------------n x n x (n+1) =n3 +n2
{
C[i, J] = C[i, J] + A[I, K] x B[K, J]; -------------------------n x n x n = n3
}
}
}
Time function (or time complexity of algorithm): F(n)= 2n3 + 2n2 + 2n+1
F(n)= Θ(n3)
Analysis Piece of Code:
For ( I= n; I > 0; I--) ---------------------------------n+1 (we will ignore this)
{
Stmt; ---------------------------------n times
}
(In analysis, we consider number of times the loop body get executed, sometimes we will ignore
the number of times the loop condition get executed).
Time function (or time complexity of algorithm): F(n)= 2n +1
F(n)= Θ(n)
