How to Analyze an Algorithm
Algorithm to swap the contents of 2 variables
Algorithm Exchange(a, b)
Begin
Tmp a ; --------------------------- 1 (unit amount of time)
a b; ------------------------------ 1
b a; ------------------------------ 1
End
Time function (or time complexity of algorithm): F(n)=3 , is constant value
F(n)= Θ(1)
Note: (Θ(1) is used to represent any constant/fixed value like 100, 200)
We are assuming that every single statement is taking unit amount of time even if it is complex
statement. We will not consider clock time.
X=4 *a + 9*b
Since we do our analysis at shallow(basic) level, therefore, we assume that the above statement
is taking unit amount or constant amount of time; although if we carefully look at this statement,
we will see that there are four operations in total. However, we ignore the detail analysis. One
can do detailed analysis up to the level of machine code.
Algorithm to sum up all the elements of Array
Algorithm sum(A, n)
Begin
s=0; --------------------------- 1
n times n+1 n times
For ( i = 0; i< n; i++) ; --------------------------- n+1 times(bother about loop condition)
Begin
S= s + A[i]; --------------------------- n times
end
Return s; --------------------------- 1 time
End
, Time function (or time complexity of algorithm): F(n)= 2n+3
F(n)= Θ(n)
Algorithm to find mean of all the elements of the Array
Algorithm sum(A, n)
Begin
s=0; --------------------------- 1
n times n+1 n times
For ( i = 0; i< n; i++) ; --------------------------- n+1 times(bother about loop condition)
Begin
S= s + A[i]; --------------------------- n times
End
mean= s/n --------------------------- 1 time
Return s; --------------------------- 1 time
End
Time function (or time complexity of algorithm): F(n)= 2n+4
F(n)= Θ(n) (Consider high order
terms only and skip the rest of the constants and variables)
Algorithm to sum up the 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] = A [I, J] + B[I, J]; -------------------------n x n
}
}
Time function (or time complexity of algorithm): F(n)= 2n2 + 2n +1
F(n)= Θ(n2)
Algorithm to swap the contents of 2 variables
Algorithm Exchange(a, b)
Begin
Tmp a ; --------------------------- 1 (unit amount of time)
a b; ------------------------------ 1
b a; ------------------------------ 1
End
Time function (or time complexity of algorithm): F(n)=3 , is constant value
F(n)= Θ(1)
Note: (Θ(1) is used to represent any constant/fixed value like 100, 200)
We are assuming that every single statement is taking unit amount of time even if it is complex
statement. We will not consider clock time.
X=4 *a + 9*b
Since we do our analysis at shallow(basic) level, therefore, we assume that the above statement
is taking unit amount or constant amount of time; although if we carefully look at this statement,
we will see that there are four operations in total. However, we ignore the detail analysis. One
can do detailed analysis up to the level of machine code.
Algorithm to sum up all the elements of Array
Algorithm sum(A, n)
Begin
s=0; --------------------------- 1
n times n+1 n times
For ( i = 0; i< n; i++) ; --------------------------- n+1 times(bother about loop condition)
Begin
S= s + A[i]; --------------------------- n times
end
Return s; --------------------------- 1 time
End
, Time function (or time complexity of algorithm): F(n)= 2n+3
F(n)= Θ(n)
Algorithm to find mean of all the elements of the Array
Algorithm sum(A, n)
Begin
s=0; --------------------------- 1
n times n+1 n times
For ( i = 0; i< n; i++) ; --------------------------- n+1 times(bother about loop condition)
Begin
S= s + A[i]; --------------------------- n times
End
mean= s/n --------------------------- 1 time
Return s; --------------------------- 1 time
End
Time function (or time complexity of algorithm): F(n)= 2n+4
F(n)= Θ(n) (Consider high order
terms only and skip the rest of the constants and variables)
Algorithm to sum up the 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] = A [I, J] + B[I, J]; -------------------------n x n
}
}
Time function (or time complexity of algorithm): F(n)= 2n2 + 2n +1
F(n)= Θ(n2)
