What is time complexity and how is it calculated?
Time complexity refers to the time needed for your program or algorithm to execute. Some programs execute faster than others, even if the end goal is the same. There are various factors involved in this time difference. For example:
- Hardware
- Operating system
- Compiler
- Size and nature of input
- Algorithm
Although some factors are hard to improve, we can certainly improve our algorithm so that it takes less time to execute.
Calculating time complexity
We determine time complexity by counting the number of the elementary operations that an algorithm takes in terms of the size of the input. First, let’s take a look at the following points:
-
Time of an algorithm is measured as a function of input size.
-
Time of an algorithm is measured in terms of the number of steps or primitive operations performed.
Example
Consider the following sum algorithm for an array:
int sum(int arr[], int n){int s = 0;for(int i = 0; i < n; i++){s = s + arr[i];}return s;}
The following steps or primitive operations were performed in this algorithm.
- In step 1, we create an integer variable named
sand initialize it with 0. - In step 2, we create an integer variable named
iand initialize it with 0. This variable is used as a counter in ourforloop. - In step 3, we perform a comparison between the variables
iandn. This comparison serves as a break condition for our loop. - In step 4, we increment the variable
iby one 1 value. - In step 5, we assign the R.H.S value of the
=operator to the variables. - In step 6, we perform addition between the value of the
svariable and value of the array at the index equal to the value of variablei. - In step 7, we get the value stored in the array at the
ith index. - In step 8, we return our variable
sto the main function.
Now, you may notice that steps 1, 2, and 8 are only executed once, irrespective of the size of the input array.
However, steps 3, 4, 5, 6, and 7 depend upon the input array’s size. For example, if there is an input array of size 5, we will execute the above steps 5 times. Thus, the number of times that these steps are executed is directly proportional to the size of the input array.
In the end, we have 3 steps that are executed once, and we have 5 steps that are executed n times. The overall time complexity of the algorithm is summarized below.
f(n) = 5n + 3
