Analysis of Algorithms

Here we are going to discuss the analysis of algorithms.

Assume that we have two algorithms for the task. We have to find out which one is better. In general, the way to do this implement both the algorithms under the two programs on your computer for different inputs and see which one takes less time.

Assume that the first algorithm takes 5 seconds to execute and the second algorithm takes 7 seconds to execute.

Now tell me which one is the better one?

Do you think the first algorithm is better than the second one?

We could not say that at this stage because there are many problems with this approach for the analysis of algorithms.

It might be possible that for some inputs first algorithm performs better than the second and for some inputs second performs better. It might be also possible that for some inputs the first algorithm performs better on one machine and the second algorithm works better on another machine for some other inputs.

What is Asymptotic Analysis?

Asymptotic analysis is a great idea that handle these kinds of issues when analyzing an algorithm. In an Asymptotic analysis, we evaluate the performance of the algorithm in terms of inputs size. Which means we don’t measure the actual running time. We calculate how does the time or space taken by the algorithm increases of inputs size.

For example, let’s consider the search problem in a sorted array. This means we have an array which is having an element in sorted order.

We can do a linear search or a binary search. To understand this example as of now you just know that linear search complexity is n and binary search complexity is log n.

class LinearSearch {
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int n[] = {1,2,3,4,5,6,7,8,9,10};
        int x = 10;
        int count = 0;
        for(int i = 1; i<= n.length; i++){
            count++;
            if(i == x){
                System.out.println("We found the value at " + count + " try");
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Time is : " + (endTime-startTime) + " ms");
    }
}

Output –

We found the value at 10 try
Time is : 0 ms

In the above example, I am calculating the complexities of linear search. As we have 10 elements in the array and we have to find its complexity we will go for the worst case. So we are searching 10 as it is present at the end in the array. And we found it on the 10th try.

Now, we will do the same using binary search.

class BinarySearch {
    static int count = 0;
    int findNumber(int[] collection, int start, int end, int x) {
        count++;
        if (end >= start) {
            int mid = start + (end - start) / 2;
            if (collection[mid] == x)
                return mid;
            if (collection[mid] > x)
                return findNumber(collection, start, mid - 1, x);
            return findNumber(collection, mid + 1, end, x);
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch obj = new BinarySearch();
        long startTime = System.currentTimeMillis();
        int[] numColl = {1,2,3,4,5,6,7,8,9,10};
        int high = numColl.length - 1;
        obj.findNumber(numColl, 0, high, 10);
        System.out.println("We found the values at " + count + " try");
        long endTime = System.currentTimeMillis();
        System.out.println("Total time :: " + (endTime - startTime) + " ms");
    }
}

Output –

We found the values at 4 try
Total time :: 1 ms

Here, we found the same value on the 4th try.

To understand how asymptotic analysis solved the problem when analyzing the algorithms, let’s consider within the linear search on your faster computer and binary search on a slow computer. For the small value of input array size n the faster the computer may take less time.

But after increasing the value of input array size i.e if it’s increased to 2000 or 10000 elements. The binary search will definitely start taking less time.

nv-author-image

Kalpesh Khairnar

Hello Everyone, I'm Kalpesh. Energetic and passionate college student with the ability to work with open-source technologies. I spend most of my time in programming, blogging and helping other programming geeks.

Leave a Reply

Your email address will not be published. Required fields are marked *