Online Classes

Results can only be achieved if you have the focused direction and crystal clear knowledge. To achieve this, you need a mentor. We will help you out by connecting with an expert mentor in the field.

Learn More

Article

Complexity of Algorithms - Codzify.com

8 min 24 sec read

How to calculate Algorithm Complexity?

 

In this article, we will learn about design and analysis of algorithm examples in Data Structures.

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");
  }
}
}
Answer:-
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
 
Answer:-
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");
      }
  }
}
}
Answer:-
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

Answer:-
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)


Answer:-
Time complexity will be O(n4)

 

Try to execute what you have learnt

Easy to use online data structure compiler where you can execute the programs in your favourite programming language.
(C, C++, Python)

Open Compiler

HTML, CSS and Javascript Real time Web Editor

Execute your HTML, CSS and javascript code in real time with the web editor
(HTML, CSS, Bootstrap, Javascript)

Open Web Editor