Time Complexity Examples 1

For Complete YouTube Video: Click Here

In this class, we will try to understand Time Complexity Examples 1.

The definition of time complexity has already been explained in our previous class.

To understand how to find an algorithm’s time complexity, consider the image below.

The above image shows the algorithm to find the sum of all elements in the array.

First, we will understand the algorithm and then find an algorithm’s time complexity.

The line of s = 0 illustrates that the initial value of the sum is 0.

The for loop iterates through all the elements of the array.

In each iteration, an element of an array is added to s.

To find the time complexity, we have to calculate the number of program steps executed to complete the algorithm’s execution.

The first line of code is executed once in the algorithm’s execution.

Next, the for loop (conditional operator of the for loop) is executed n + 1 times.

Why n + 1 times?

The n times to iterate through all the elements of the array.

The last execution is the failure case of the loop where all the n elements are used to sum.

The line of code sum = sum + a[i] is executed n times.

The return statement is executed only once.

The number of times each step of the algorithm is executed is shown below.

The time complexity of the algorithm is 1 + n + 1 + n + 1 = 2n + 3.