What is meant by the Time Complexity of an

Algorithm?
Now, the question arises if time complexity is not the actual time required to
execute the code, then what is it?
The answer is:
Instead of measuring actual time required in executing each statement in the
code, Time Complexity considers how many times each statement
executes.
Example 1: Consider the below simple code to print Hello World
 C code

#include <stdio.h>

int main()

printf("Hello World");

return 0;

Output
Hello World
Time Complexity: In the above code “Hello World” is printed only once on
the screen.
So, the time complexity is constant: O(1) i.e. every time a constant amount
of time is required to execute code, no matter which operating system or
which machine configurations you are using.
Example 2:
 C Code

#include <stdio.h>

void main()

{
 int i, n = 8;

for (i = 1; i <= n; i++) {

printf("Hello World !!!\n");

Output
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Time Complexity: In the above code “Hello World !!!” is printed only n
times on the screen, as the value of n can change.
So, the time complexity is linear: O(n) i.e. every time, a linear amount of
time is required to execute code.
Example 3:
 C Code

#include <stdio.h>

void main()

int i, n = 8;

for (i = 1; i <= n; i=i*2) {

printf("Hello World !!!\n");

// This code is contributed by Suruchi Kumari

Output
Hello World !!!
Hello World !!!
Hello World !!!
Hello World !!!
Time Complexity: O(log2(n))
Example 4:
 C Code

#include <stdio.h>

#include <math.h>

void main()

int i, n = 8;

for (i = 2; i <= n; i=pow(i,2)) {

printf("Hello World !!!\n");

Output
Hello World !!!
Hello World !!!
Time Complexity: O(log(log n))
 How To Find The Time Complexity Of An
Algorithm?
Now let us see some other examples and the process to find the time
complexity of an algorithm:
Example: Let us consider a model machine that has the following
specifications:
 Single processor
 32 bit
 Sequential execution
 1 unit time for arithmetic and logical operations
 1 unit time for assignment and return statements
Q1. Find the Sum of 2 numbers on the above machine:
For any machine, the pseudocode to add two numbers will be something like
this:

 C

Pseudocode : Sum(a, b) { return a + b }

Time Complexity:
 The above code will take 2 units of time(constant):
 one for arithmetic operations and
 one for return. (as per the above conventions).
 Therefore total cost to perform sum operation (Tsum) = 1 + 1 = 2
 Time Complexity = O(2) = O(1), since 2 is constant
Q2. Find the sum of all elements of a list/array
The pseudocode to do so can be given as:

 C

Pseudocode : list_Sum(A, n)

// A->array and

// n->number of elements in array

sum = 0
 for i = 0 to n-1

sum = sum + A[i]

return sum

To understand the time complexity of the above code, let’s see how much
time each statement will take:

 C

Pseudocode : list_Sum(A, n)

total =0 // cost=1 no of times=1

for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the

sum = sum + A[i] // cost=2 no of times=n

return sum // cost=1 no of times=1

Therefore the total cost to perform sum operation