Analysis of algorithm

The Idea of Analysis of the algorithm is all about ways of accomplishing a problem, let's take an example:

Abhi travel between two cities, he goes from "Kolkata" to "Delhi", there can be many ways of traveling: by train, by car, by bus, by flight, by train and also by walking. Depending on the convenience and availability, we choose according to our choice it depends on us. In programming or computer science similarly, there are multiple algorithms are available for solving a problem, for example, let's take another example :

there are two students each of them writes a program - "Sum of n Natural Numbers"

Students 1 :

void sum (int n)
{
    return n*(n+1)/2;
}

Students 2:

void sum (int n)
{
    int sum = 0;
    for(int i = 1;i<=n;i++)
    {
        
        sum += i ;
    
    }
    
    return sum;
}

now see, both of them solve the same problem but in two different ways, student 1 just return an operation value recursively that is the formula of "Sum of n Natural number", Student 2 iterate i=1 to n and add the value of "i" in "Sum" variable, now the most important question is which solution takes less time to execute.

Now this question's answer depends on two major factors, first one is time depends on the machine where the program runs means if you have the most efficient machine then it may take less time. The second one is the program you make now the question comes, how we know which program takes less time and for this reason, we analysis the algorithm written over a program.

Here we analyze the above-mentioned programs, before going to discuss the problems or better say analyze those two programs, we need to know about Asymptotic Analysis. Now if we have enough idea of asymptotic analysis, let's deep dive into those two problems,

void sum (int n)
{
    return n*(n+1)/2;
}

Time Taken : T1

this program was written by Student 1, this student just returns a calculative value recursively, let this program takes T1 time, now this program returns the value which includes three operations (multiplication + summation + division ), but as we know any kind of mathematical operation takes constant times irrespective to the input value, if we add 1+1 and 1^10 + 1^50 both of them takes the same time.

on the other hand, we have another program was written by student 2 :

void sum (int n)
{
    int sum = 0;
    for(int i = 1;i<=n;i++)
    {
        
        sum += i ;
    
    }
    
    return sum;
}

Time taken: T2*n + T3

here two types of work are running, the first one is iterative and the second one constant, now T2*n time takes by the for loop and other work is some cumulative constant taken by the program that denoted by T3 .

When we analyze a program we have to check the Order of growth. In our two problems we have to check the order of growth as well, when we analyze two programs.

Now, the total idea of analysis of algorithm si the process of determining how time increases as the size of the problem increases. Input size is the number of elements in the input , and depending on the problem type , the input may be of differsent size and types

• Vertices and edges in a graph.

• Number of elements in a matrix

• Polynomial degree

• Size of an array

• Number of bits in the binary representation of the input