# How to calculate the complexity of Algorithms?

Article by: Manish Methani

Last Updated: October 8, 2021 at 2:04pm IST

# How to calculate Complexity of Algorithms?

## Example 1 :-

What will be the Time Complexity of given program ?

displayFunction()
{
int i,j;
for(int i = 1; i<=n; i++)
{
for(int j = 1; j<= n; j++)
{
printf("Analyse me");
}
}
}
Time Complexity of this program will be O(n2)

First for loop will execute 1 to n times. Right? For each value of i, j loop will execute n times.

So,
i = 1
j will execute n times and prints Analyse me.

i = 2,
j will execute n times and prints Analyse me

j = 3,
j will execute n times and prints Analyse me
.
.
.
i = n,
j will execute n times and prints Analyse me

Time complexity  = n*n
= n2

## Example 2:-

What will be the Time Complexity of given program ?

First for loop will execute n times. j loop is dependent on value of i. k is independent loop.

\$\$Note: 1+2+3+...+n = dfrac{n(n+1)}{2}\$\$

displayFunction()
{
int i,j,k,n;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=i; j++)
{
for(int k=1; k<=100; k++)
{
printf("Analyse me");
}
}
}
}
Time Complexity of this program will be O(n2)

To solve these kind of problems analyse by placing values.

i=1               i=2             i=3
j=1 time          j=2 times       j=3 times
k=1*100 times     k=2*100 times   k=3*100 times

i=n
j=n times
k=n*100 times

So,
100*1 + 2*100 + 3*100 +......+n*100
100(1 + 2 + 3 + ...... + n)
100((n(n+1))/2)
100* n2

So time complexity will be O(n2)

## Example 3:-

What will be the Time Complexity of given program ?

First for loop will execute n times. j loop is dependent on value of i and executes i2 times. k is independent loop executes based on j loop and executes as many times as j loop satisfies the condition.

\$\$Note: 1^2+2^2+3^2+...+n^2 = dfrac{n(n+1)(2n+1)}{6}\$\$

displayFunction()
{
int i,j,k,n;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=i2; j++)
{
for(int k=1; k<=n/2; k++)
{
printf("Analyse me");
}
}
}

To solve these kind of problems analyse by placing values.

i=1               i=2               i=3
j=1 time          j=4 times         j=9 times
k=1*(n/2) times   k=4*(n/2) times   k=9*(n/2) times

i=n
j=n2 times
k=n2*(n/2) times

So,
(n/2)*1 + 4*(n/2) + 9*(n/2) +......+n2*(n/2)
(n/2)(1 + 4 + 9 + ...... + n2)
(n/2)(n(n+1)(2n+1))/6)

Time complexity will be O(n4)

## Simplified Coding for Beginners.

Mobile App Development, Web App Development, Programming Languages, Latest Tech News & lot more.

## The Complete Angular Course

Instructor: Manish Methani

Free

## C Programming for Absolute Beginners

Instructor: Manish Methani

## Flutter Mobile App Development Course

Instructor: Manish Methani

Free

## Learn HTML, CSS & Bootstrap

Instructor: Manish Methani

## C Programming Test

Test your C Programming skills with this comprehensive mock test on C Programming.

## Flutter Test

Solve most asked Interview Questions on Flutter and Test your foundational skills in flutter.

## GATE(CSE) Operating Systems

Solve most asked GATE Questions in Operating Systems and test your Gate Score.

## HTML,CSS Test

This is a mock test designed to help you assess your knowledge and skills in HTML and CSS.

## (GATE CSE) Data Structures & Algorithms Test

Solve most asked GATE Questions in Data Structures and Algorithms and test your Gate Score.

include_once 'codzify-footer.php'; ?>