Tutorial 04: Analysis of Time Complexity
- Running time depends many factor but we compute it based on input size.
- So, we need to calculate the rate of growth of time w.r.t input.
Assumptions:-
- All arithmetic and logical operations taking 1 unit of time.
- All return statement also taking 1 unit of time.
Example of Constant Time:-
int sumOfNumber(a,b)
{
c = a + b; —–> 1 +1 = 2 unit of time
return c; —–> 1 unit of time
}
Total cost 2 +1 = 3 unit of time
it means constant unit of time
Example of Linear Time:-
int sumOfArray(a[ ], n) Cost Number of Time
{
int sum=0; 1 1
for(int i = 0; i < n; i++ ) 2 n+1
{
sum=sum+a[i]; 1 n
}
return sum; 1 1
}
Total Cost = 1+2(n+1)+2(n)+1 = 4n+4
This is called Linear Time
Analysis of Time Complexity
- T(n) = 3 unit = constant = O(1)
- T(n) of sumOfArray = 4n+4 = linear = O(n)
- T(n) of Matrix Multiplication = an^2 + bn +c = quadratic = O(n^2)
big Oh, big omega and big theta are asymptotic notation
Asymptotic Notations:-
- Asymptotic analysis of an algorithm refers to defining the mathematical boundation of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case scenario of an algorithm.
- Usually, the time required by an algorithm falls under these three types:-
- Best Case – Minimum time required for program execution.
- Average Case – Average time required for program execution
- Worst Case – Maximum time required for program execution
