Question 97 : What is an algorithm and how to calculate complexity of algorithms.

How will you calculate the complexity of the algorithm” is a very common question in interviews. 

How will you compare the two algorithms? 
How does running time get affected when the input size is quite large? 

So these are some question which is frequently asked in interview. In this post, We will have a basic introduction to the complexity of the algorithm and also too big o notation

What is an algorithm?

An algorithm is step-by-step instructions to solve a given problem.

Let's take a simple example. You want to write an algorithm for listening particular song.

1) Search for songs on the computer.

2) Is the song available?

            i.If Yes, Then listen to that song.

           ii. If no, download that song and then listen to that song.

So we are solving a problem by step by step procedure. These step-by-step instructions are called algorithms.

Why do you need to evaluate an algorithm?

You need to evaluate an algorithm so that you can find the most optimized algorithm for solving a given problem and also consider various factors and constraints.

For example:

You want to go from city A to City B.Then there are various choices available i.e. by flight, bus or train. So you need to choose among different options depending on your budget and urgency.

Counting number of instructions:

A number of instructions can be different for different programming languages.

Let's count the number of instructions for searching an element in an array.

int n=array.length
for (int i = 0; i < n; i++) {
 
 if(array[i]==elementToBeSearched)
 return true;
 }
 return false;

Let’s assume our processor takes one instruction for each of the operation:

• For assigning a value to a variable
• For comparing two values
• Multiply or addition
• Return statement

In the Worst case:

If the element which we want to search is the last element in the sorted array then it will be the worst case here.
So :

:

if(array[i]==elementToBeSearched) ,i++ and i<n <b>will be executed n times</b>
int n=array.length,i=0,return true or false <strong>will be executed one time.
</strong>

Hence f(n)=3n+3

Asymptotic behaviour :

Here We will see how f(n) performs with the larger value of n. Now in the above function, we have two parts i.e. 3n and 3. Here you can note two points:

• As n grows larger, we can ignore constant 3 as it will be always 3 irrespective of the value of n. It makes sense as you can consider 3 as the initialization constant and different languages may take different times for initialization. So the other function remains f(n)=3n.
• We can ignore constant multiplier as different programming languages may compile the code differently. For example, array lookup may take a different number of instructions in different languages. So what we are left with is f(n)=n

How will you compare algorithms?

You can compare algorithms by its rate of growth with input size n

Let's take a example.For solving same problem, you have two functions:

f(n) =4n^2 +2n+4 and f(n) =4n+4

For f(n) =4n^2² +2n+4
so here
f(1)=4+2+4
f(2)=16+4+4
f(3)=36+6+4
f(4)=64+8+4
….
As you can see here the contribution of n^2² increases with an increasing value of n.So for a very large value of n, contribution of n^2 will be 99% of the value on f(n).

So here we can ignore low order terms as they are relatively insignificant as described above.In this f(n),we can ignore 2n and 4.so
n^2+2n+4 ——–>n^2

For f(n) =4n+4
so here
f(1)=4+4
f(2)=8+4
f(3)=12+4
f(4)=16+4
….
As you can see here the contribution of n increases with the increasing value of n.So for a very large value of n, the contribution of n will be 99% of the value on f(n).

So here we can ignore low-order terms as they are relatively insignificant. In this f(n),we can ignore 4 and also 4 as a constant multiplier as seen above so
4n+4 ——–>nSo here n is the highest rate of growth.

Point to be noted :
We are dropping all the terms which are growing slowly and keep one which grows fastest.

Big O Notation:

This notation is used for a theoretical measure of execution of an algorithm. It gives a tight upper bound of a given function. 

Generally, it is represented as f(n)=O(g(n)) and it reads as “f of n is big o of g of n”.

Formal definition:

f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. The values of c and n0 must not be dependent on n.

When you say O(g(n)) , It means it will never be worst than g(n). 
Having said that it means O(g(n)) includes smaller or same order of growth as g(n).

So O(n) includes O(n),O(logn) and O(1).
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=5n
Writing in a form of f(n)<=c*g(n) with f(n)=4n+3 and g(n)=6n

so there can be multiple values for n0 and c for which f(n)<=c g(n) will get satisfied.
Writing in a form of f(n)<=c*g(n) with f(n)=4n^2 +2n+4 and g(n)=5n^2
4n^2 +2n+4<=5n^2 for n0=4 and c=5

So O(g(n)) is a good way to show the complexity of algorith
Let's take some examples and calculate a value for c and n0.

1. f(n)=4n+3
4n+3<=5n for n0=3 and c=5.
or 4n+3<=6n for n0=2 and c=6

2. f(n)=4n^2+2n+4

Rules of thumb for calculating the complexity of an algorithm:

Simple programs can be analyzed using counting the number of loops or iterations.

Consecutive statements:

We need to add the time complexity of consecutive statements.

f(n)=c1+c2;
So O(f(n))=1

Calculating complexity of a simple loop:

Time complexity of a loop can be determined by running time of statements inside loop multiplied by total number of iterations.

 int m=0; // executed in constant time c1
         // executed n times
         for (int i = 0; i < n; i++) {
             m=m+1;  // executed in constant time c2
  }
 

f(n)=c2*n+c1;
So O(n)=n

 

Calculating the complexity of a nested loop:

It is a product of iterations of each loop.

:

  int m=0; executed in constant time c1
          // Outer loop will be executed n times 
   for (int i = 0; i < n; i++) {
          // Inner loop will be executed n times
  for(int j = 0; j < n; j++)
  {
   m=m+1; executed in constant time c2
  }
 }

f(n)=c2*n*n + c1
So O(f(n))=n^2

 

If and else:

When you have if and else statement, then time complexity is calculated with whichever of them is larger.

        int countOfEven=0;//executed in constant time c1
        int countOfOdd=0; //executed in constant time c2
           int k=0; //executed in constant time c3
//loop will be executed n times  
  for (int i = 0; i < n; i++) {
          if(i%2==0) //executed in constant time c4
            { countOfEven++; //executed in constant time c5
              k=k+1; //executed in constant time c6
            }
          else
            countOfOdd++; //executed in constant time c7
 }
 

f(n)=c1+c2+c3+(c4+c5+c6)*n
So o(f(n))=n

Logarithmic complexity

Let's understand logarithmic complexity with the help of an example.You might know about binary search. When you want to find a value in a sorted array, we use a binary search

Now let’s assume our sorted array is:

int[] sortedArray={12,56,74,96,112,114,123,567};

and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iterations you are cutting the scope of array to the half. In every iteration, we are the overriding the value of first or last depending on soretedArray[mid].

So for
0th iteration : n
1th iteration: n/2
2nd iteration n/4
3rd iteration n/8.
Generalizing above equation:
For ith iteration : n/2ⁱ

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:
1=n/2ⁱ;
2ⁱ=n;
after taking log
i= log(n);

so it concludes that the number of iterations requires to do binary search is log(n) so the complexity of the binary search is log(n)

It makes sense as in our example, we have n as 8 . It took 3 iterations(8->4->2->1) and 3 is log(8).
So If we are dividing input size by k in each iteration,then its complexity will be O(logk(n)) that is log(n) base k.

Lets take an example::

 int m=0; 
         // executed log(n) times
         for (int i = 0; i < n; i=i*2) {
             m=m+1; 
  }

The complexity of the above code will be O(log(n)).

Exercise:
Let's do some exercises and find the complexity of the given code:

1,

int m=0; 
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }

Complexity will be O(n)

2.

int m=0;
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
   for (int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++)
             m=m+1; 
  }
}

Ans:

     int m=0;
       // Executed n times
         for (int i = 0; i < n; i++) {
             m=m+1; 
  }
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // inner loop executed n times
       for(int j = 0; j < n; j++)
             m=m+1; 
  }

Complexity will be :n+n*n —>O(n^2)

3.

        int m=0;
       
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
          for(int k=0;k*k < n; k++ )
             m=m+1; 
  }
        }
}
\
:

Ans

 int m=0;
       
    // outer loop executed n times
   for (int i = 0; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
      // inner loop executed log(n) times
          for(int k=0;k*k < n; k++ )
             m=m+1; 
  }
       }
}

Complexity will be n*n/2*log(n)–> n^2log(n)

 4.

int m=0;
    
   for (int i = n/2; i < n; i++) {
       for(int j = n/2; j < n; j++)
          for(int k=0;k < n; k++ )
             m=m+1; 
  }

Ans:

int m=0;
       
    // outer loop executed n/2 times
   for (int i = n/2; i < n; i++) {
 // middle loop executed n/2 times
       for(int j = n/2; j < n; j++)
      // inner loop executed n times
          for(int k=0;k < n; k++ )
             m=m+1; 
  }

Complexity will be n/2*n/2*n –> n^3