Time Complexity of an Algorithm
- Time Complexity: Total running time of an algorithm depends upon execution of compilation time and running time of an algorithm but once program is compile can be run several times so i.e we discuss and concern with the runtime of the Algorithm.
- As you Know the complexity of an algorithm is amount of time needed by an algorithm to Execute. this is called Time Complexity.
- In this post you will be able to obtain time complexity of an Algorithm.
- We can obtain some general formula or methods for all arithmetic operation which perform at runtime is given by as follows:
T(n) = C1 Mul(n) + C2 Add(n) + C3 Sub(n)+...........................................+Cn Mul(n)
Here T denotes for time complexity and C1, C2, C3,Cn denotes for the cost taken by the
Algorithm to execute .
- Lets take an Example to calculate the time Complexity of the Algorithm as follows.
Main() Time Cost
{
int a,b,c,d,i; 1 C1
for(i=0;i<=10;i++) 11 C2
{
a=a+b; 10 C3
b=b+1; 10 C4
}
d=c+d; 1 C5
}
1. Here you will get how the lines are executing and taking the Time . In the above
example You will notice that 1st & 5th Line are under main method taking time 1 and
2nd Line taking time 11 and 3rd & 4th Line are taking time 10 .
2. Don't be Confuse Why For-loop line 2nd taking time 11 and 3rd & 4th Line under loop are
taking 10 because Firstly, 2nd line compile 1 time by the compiler and Secondly, 2nd line
Compile 10 times again to compile 3rd & 4rth Line so that is why for-loop the 2nd Line is
compiling 1 time more than 3rd & 4rth Line.
- Now Calculating Time Complexity of above example.
=> T(n) = C1*1 +C2*11 + C3*10 + C4*10 + C5*1
=> T(n) = 1*(C1+C5) + 10*(C3+C4) + C2 * 11
=> T(n) = O(11) <----------ans .="." div="div">
1. Here The Time complexity expressed in Big O-Notation.
2. Time Complexity of the above Algorithm is 11.
3. Remember we always take highest Time taken value in big O notation to describe time
complexity of the Algorithm.Here we get C2*11 which is describing the highest time
taken by above Algorithm is 11 i.e O(11).
- Similarly Now we will calculate the time complexity of n time terms of an Algorithm as follow:
main() Time Cost
{
int i,j,k,n; 1 C1
i=i+1; 1 C2
for(i=1;i<=n;i++) n+1 C3
{
j=j+1; n C4
}
k=k+1; 1 C5
}
1. Now through Previous example you are able to know Line number 1st ,2nd and ,5th are
running 1 time only in current example.
2. Line number 3rd running n+1 times in the algorithm.Similarly inside For-loop line
number 4rth is running n times in the algorithm.Now you can notice as in previous example
For-loop firstly compile 1 time by compiler and Secondly n times again with line number
4rth i.e Why Line number 3rd running n+1 times.
- Therefore calculating above example time complexity with respect to n times term used in algorithm as follows:
=> T(n) = C1*1 + C2*1 + C3*(n+1) + C4*n + C5*1
=> T(n) = 1*(C1 + C2 + C5) + C3*n+C3*1 + C4 *n
=> T(n) = 1*(C1+C2+C3+C5) + n*(C3 + C4)
=> T(n) = 1*(C1+C2+C3+C5) + n*(C3 + C4)
=> T(n) = O(n) <----------------ans .="." br="br"> 1. As you know time Complexity is expressed in big O-notation.
2. Here time complexity of the recent algorithm is O(n).
3. In this Algorithm bigger value is n*(C3+C4) where getting highest time taken is n i.e why
value is O(n).
4. Don't Confuse that Expression was C3*(n+1) so value should be O(n+1)but it is not.
Value will be O(n) because when it is fully simplify it will give result n*(C3+C4) i.e only
n term value should be used in big O Notation.
2. Here time complexity of the recent algorithm is O(n).
3. In this Algorithm bigger value is n*(C3+C4) where getting highest time taken is n i.e why
value is O(n).
4. Don't Confuse that Expression was C3*(n+1) so value should be O(n+1)but it is not.
Value will be O(n) because when it is fully simplify it will give result n*(C3+C4) i.e only
n term value should be used in big O Notation.
- Now we will deal with little complicated Example to find out Time Complexity of an Algorithm.
main() Time Cost
{
int i,j,a,b; 1 C1
for (i=1;i<=n;i++) n+1 C2
{
for(j=1;j<=m;j++) n*(m+1) C3
{
a=a+1; n*m C4
}
b=b+1; n C5
}
}
1. Line number 1st in the algorithm is running 1 time.
2. Line number 2nd in the algorithm is running n+1 times i.e firstly this line one compile by
compiler and Secondly it runs n times more to run 3rd and 4rth Line in the algorithm.
3. Line number 3rd in the algorithm running n*(m+1) times i.e Firstly For loop is run n times
and Secondly it runs n*m times more to run run line number 4rth in the algorithm.
4. Line number 4rth run by both loops n*m times in the above algorithm
5. Line number 5th run n times by line number 2nd in the algorithm.
=> T(n) = C1*1 + C2*n + C2*1 +C3*(nm + n) + C4*nm +C5*n
=> T(n) = 1*(C1+C2) + n*(C2 + C3 + C5) + nm*(C3 + C4)
=> T(n) = O(nm) <-----------------------ans .="." br="br">
1. In above calculation time complexity is expressed in big O notation.
2. Time complexity of the above algorithm is O(nm).
3. As you Notice in above expression the highest value is nm*(C3+C4) therefore value of the time complexity
of above algorithm is O(nm).
1. Line number 1st in the algorithm is running 1 time.
2. Line number 2nd in the algorithm is running n+1 times i.e firstly this line one compile by
compiler and Secondly it runs n times more to run 3rd and 4rth Line in the algorithm.
3. Line number 3rd in the algorithm running n*(m+1) times i.e Firstly For loop is run n times
and Secondly it runs n*m times more to run run line number 4rth in the algorithm.
4. Line number 4rth run by both loops n*m times in the above algorithm
5. Line number 5th run n times by line number 2nd in the algorithm.
- Calculating the time complexity of the above algorithm of the post as follows:
=> T(n) = C1*1 + C2*n + C2*1 +C3*(nm + n) + C4*nm +C5*n
=> T(n) = 1*(C1+C2) + n*(C2 + C3 + C5) + nm*(C3 + C4)
=> T(n) = O(nm) <-----------------------ans .="." br="br">
1. In above calculation time complexity is expressed in big O notation.
2. Time complexity of the above algorithm is O(nm).
3. As you Notice in above expression the highest value is nm*(C3+C4) therefore value of the time complexity
of above algorithm is O(nm).
