Analysis of Algorithm - Java

 

I was getting comments on it to explain the concept. I have tried to capture my concept on paper but it could have better on video and will upload the video ASAP.

Analysis of the algorithm:

In this article, I will try to give you brief in the easiest way possible and also write 3 functions/methods that return the sum of first n natural numbers and using these functions I will explain the concept of it. It is very basic but very important to understand others you will be confused like what is the difference between Big O of N and Theta of  N. Most people fail to explain it. here I will stick to my topic and will try not to go beyond.

and analyze these different functions in detail and compare them with each other on the basis of the time taken by them individually.

Let's understand the analysis with this example.

Given a number n, write a function/method to find the sum of first n natural numbers. very simple right?

I/P= n= 3

O/P = 6

I/P= n= 5

O/P = 15

So it is like if n =3 then 1+2+3 = 5 sum of first natural numbers right?

And if n =5 then it is like 1+2+3+4+5 =15

So now I am gone a write 3 different solutions for this program and try to analyze it.

Soution 1 :

int fun(int n)

{

  return n*(n+1)/2 ;

}

What it does?:

it simply uses the formula of first n natural numbers So like the first 3 natural numbers you will do like 3*(3+1)/2 = 6

Solution 2:

int fun2(int n)

{

  int sum = 0;

  for(int i=0;i<=n ; i++)

  {

    sum = sum + i ;

  }

  return sum;

}

What it does?

is like simply runs a loop to sum numbers from 1 to n. 

Solution 3:

int fun3(int n)

{

  int sum =0;

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

      for(int j=1 ; j<=i; j++)

  sum ++;

 return sum;   

}

what it does?

it goes from i to 1 to n and for every i it increments the sum by i times.

1 + (1+1) + (1+1+1) for n =3 

Now how would you decide which one is better among all these functions?

The analysis which handles all these 3 functions is called Asymptotic analysis and basically, we measure the order of growth of a program or an algorithm in terms of input size.

So here I am writing an expression for the time taken by these 3 different functions

fun1() - > c1

fun2() - > c2n + c3

fun3() - > c4n^2 + c5n + c6

where c1,c2,c5,c6 all are constants 

n = input size for the program.

Now I am going to tell you how to get these expressions. So the first function does the constant work however how? like if you pass n = 10000 then also it will compute like

10000*(10000 + 1)/2 right? and even if you pass 100 it will do the same way right? So no matter what you pass as input size the number of operations you are doing is constant and it is not dependent upon the value of its input size And what operations you are doing So what are the operations here you are doing is like one initiation, one multiplication, and one division right?

these 3 operations are not dependent upon anything it will be the same for 10, 100, 1000, 1000000, etc right? and that is why I have written constant C1 on the above expression for that function .

Now let see function2 and think why we do get c2n + c3 SO in this function we do some constant amount of work here like 

int fun2(int n)

{

  int sum = 0;                  // 1) this is a constant work right?

  for(int i=0;i<=n ; i++)       //2) the initialization of i is also constant work

  {

    sum = sum + i ;             // 3)Similarly it is also a constant work 

  }

  return sum;

}

So why I am always saying constant work because it will always happen exactly once whether you pass n = 10, n= 1000, n =1000000000, etc. it will not depend on input size right? but there is some work which depends upon the input size n. 

sum = sum + i  // this will execute the 100 times if n=100 and ten thousands time if n = 10,000 right?

 Similarly this for(int i=0;i<=n ; i++) // this i++ will  also depend upon the input size of the n . it will also increment based on the input size right?

 Similarly, the condition checks i<=n will also depend on the input size right?

 So there is some work which happens constant times So if I write it C2 time and the rest of the work is constant time So we can write  it as C2n + C3

Now analyze the function 3 what happens in this case is 

int fun3(int n)

 {

  int sum =0;

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

      for(int j=1 ; j<=i; j++)

  sum ++;    

  return sum;   

 }

this sum ++ is going to happen how many times? It will happen n * (n+1)/2 times right? If you notice the program the inner loop will run for  i=1 for 1 time and i=2 for 2 times and so on right? So it is going to run 1 + (1+1) + (1+ 1+ 1) So ultimately you have an expression which runs 

 n *(n + 1)/2 and you have more expression like you constant works also right So we can write it as 

 n*(n+1)/2 + Constant

 So now whenever you think of analysis of algorithm always think of the size of input which is larger than or equal to zero because your input size can never be negative.

 And also the time taken by the function be should greater than or equal to zero because your algorithm or program can never take a negative time.

 So now see the static analysis all those above programs may work faster for small input size may be the function 2 or function 3 works faster for the small input size but when you increment the input size like 10000000 than you will notice actually the function 2 and function 3 is taking more than function 1.So one more thing the function 1 will always give you the linear time taken to execute the program as it does not depend on the input size like I explained above.

 There are mathematical ways of analysis also for comparing which algorithms are better and we measure it in terms of the order of growth.

So this is how you compare which algorithm is better and which is not? keep in mind that it also depends upon the programming language and the machine that you use to compare the algorithms.

And one more point the Big O of N gives you the probable complexity whereas Theta of N will give you the exact complexity and information of the algorithm.I can discuss more on this but in the next blog will tell what is the difference when I say Big O of N and Theta of N of an Algorithm.