Question

Question Q/ What have you learned about being able measuring an algorithm and why it is important?

Answer 1

=> An algorithms are the step by step process of solving any complex problem, For a single problem we can have many solutions or we can say many algorithms. So here question is that how we can define which one is the best algorithms. There are two important things which we follow while algorithms analysis.

1)- Space used

2)- Running Time.

Any algorithms which solve the problem using less space and less time, so that algorithms will be the best algorithms.

Please see below code-

int sum(int arr[], int sizeOfArray){

int temp =0;

for(int i=0;i < sizeOfArray; i++){

temp = temp+arr[i];  

}

return temp;

}

Here in above code initialization of "temp" and return statement will take the equal time for all the input, so it is constant for all but the code inside the loop statement is directly depends on the problem size.

So for analysis of any algorithms, we have three cases

1)-Best Case

Let's consider a balanced binary tree, all the elements are equally distributed like below

Here search time complexity is always O(log n)

2)-Worst Case

If the tree is left or right skewed then we need to iterate all the list so worst case will be O(n).

  

3)Average case

In the average case, it will be O(log n).

Why Measure of Algorithms is Important?

It's very important to measure of algorithms because we can solve a problem many ways but we always select the best way.

Let suppose we have one sorted array and our task is to find the availability of an element into the array. So we can find it two ways

1)- Leaner Way

int search(int arr[], int n, int x)

{

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

        if (arr[i] == x)

         return i;

    return -1;

}

The running time complexity of above code is always O(n), because we have to iterate whole list.

2)- Binary Search

int binarySearch(int arr[], int l, int r, int x)

{

   if (r >= l)

   {

        int mid = l + (r - l)/2;

if (arr[mid] == x)  

            return mid;

if (arr[mid] > x)

            return binarySearch(arr, l, mid-1, x);

return binarySearch(arr, mid+1, r, x);

   }

return -1;

}

The running time complexity for above code will be O(log n) which is very minimum.

So in the above code, we are given solution for the same problem but the second one is more efficient than first. Measurement of an algorithm is very important.