In this chapter we shall learn about
3.1 Example 1
3.2 Example 2
3.3 Below are different types of time function available.
3.4 Increasing order of time consumption
In the last chapter we learnt on how to calculate space complexity. In this chapter we shall learn on how to calculate time complexity.
3.1 Example 1
Let us take the same previous example to calculate the sum of “n” numbers in the array and how much time will it take to get the result.
Pseudo code:
int calculate_sum(int arr[], int length) { int total_sum = 0; int i = 0; for( i= 0; i< len; i++) { total_sum = total_sum + arr[i]; } }
For space complexity we take the variables, but for calculating time complexity we concentrate of the number of statements executed.
From the above code, we can calculation as:
The statement “int total_sum = 0;” will be executed 1 time. Hence 1 unit.
The statement “int i = 0;” will be executed 1 time. Hence 1 unit.
The statement “for( i= 0; i< len; i++)” will be executed “len+1” times. This is because, it will also calculate till, after the condition is false.
The statement “total_sum = total_sum + arr[i];” will execute “len” times.
Hence the total time taken to execute is = “2n+3”. For larger value of n, we ignore the constants, hence the final time complexity is “O(n)” times.
3.2 Example 2
Time complexity for matrix addition:
Pseudo code:
int add_matrix( int a[m] [n], int b [m] [n], int m, int n) { for (i = 0; i< n; i++) { for(j = 0; j<n; j++) { c[i][j] = a[i][j] + b[i][j] } }
From the above code, we can see that:
The first for loop “for (i = 0; i< n; i++)” will be executed (n+1) time. Hence n+1 units.
The second for loop “for(j = 0; j<n; j++)will be executed n*(n+1) time. Hence n(n+1) units.
The third statement “c[i][j] = a[i][j] + b[i][j]” will be executed “n * n” times. Hence n^2 units.
i.e
n+1+ n^2+n + n^2
2n^2 + 2n + 1
For larger value of “n” we ignore the constants, hence total time taken to execute is O(n^2).
Usually when we are trying to calculate the time complexity, we try to relate to the time functions we know.
3.3 Below are different types of time function available:
O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(n^3)
O(2^n)
O(3^n)
O(n^n)
3.4 Below is the increasing order of time consumption:
O(1) < O( log n) < O(n)< O( nlog n) < O(n^2) < O(n^3) < O(2^n) < O(3^n) < O(n^n)
AJ’s guide for DS and Algorithms..Click here to study the complete list of algorithm and data structure tutorial. 85+ chapters to study from.
Rushil
In the order of time complexity, O(nlogn)>O(n) na?
prodevelopertutorial
True, changing now
Nikhil
for (i = 0; i< n; i++)
Why would this loop execute n+1 times?
Shouldn't it be n times
prodevelopertutorial
it is because, to check the exit condition.
donReddy
Sir, can you plz add some more examples with explanations plzz.. Your tutorials are very nice and easy to understand but needed little more explanation on this topic plz.