Skip to main content

Asymptotic Analysis of Algorithms

 
In Asymptotic analysis, We evaluate the performance of an algorithm by the input size, not by the actual running time.
For example, if we want to search an item from an sorted array, we can do this by two ways:
  • Linear Search - Takes linear time.
  • Binary Search -Takes logarithmic time
Now let's assume we are running the linear search in a fast computer and the binary search in a slow computer. For small inputs, the fast computer may take less time to find the item, but as the input size increases and for a larger input the slow computer with binary search will take less time to find the item. The reason is that binary search takes logarithmic time. So, the machine dependency can be ignored after a certain size of inputs.

So, is it always gives perfect result?
No. But that's the best way available to evaluate an algorithm. Let's say, two algorithms take
  1. 2000nLogn
  2. 5nLogn
In asymptotic analysis, we always ignore constants. So, both of the above becomes:
  1. nLogn
  2. nLogn
In that case, we can't evaluate which one works faster.

Cases: Worst, Best, and Average 

There are three ways to evaluate an algorithm.
  1. Worst Case (Most cases we do Worst case analysis)
  2. Average case (Sometimes)
  3. Best Case (Usually not done to evaluate an algorithm)
Let's take an example of Linear Search (Python code given below):


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
''' 
Linear search example 
Time complexity O(n)
'''


def search_item(array_list, search_element):
    found = False
    for i in range(len(array_list)):
        if array_list[i] == search_element:
            found = True
            print(f"Element {search_element} found at position {i+1}")
            break
    if found == False:
        print(f"{search_element} is not found in the array list")


if __name__ == "__main__":
    array = [4, 2, 8, 9, 3, 7]
    search_element = 9
    search_item(array, search_element)

'''
output: 
Element 9 found at position 4  
'''

Worst Case Analysis:

In this case, we calculate the upper bound of running time, cases that take maximum number of operations. Like, if anyone asks, what will be the maximum time it will take to be executed?
We answer this question by doing worst case analysis.

In Linear Search, worst case happens when the searched item is not present in the List/ Array.
In this case, every elements need to compare with the searched item. So, it takes time equal to number of List / Array elements. 

Here, time complexity would be:  ϴ(n).  for total n elements.

Average Case Analysis:

In this case, we take all possible inputs and calculate time for all the inputs. Then, we sum all the calculated values and divide it by the total number of inputs. This is not easy to do, we have to know all mathematical distributions of input values. It is rarely done.

Best Case Analysis:

We calculate the lower bound of running time, cases that take minimum number of operations.
In Linear Search, Best case happens when the searched item present in the 1st position of a List  / Array. 

Here, time complexity would be:  ϴ(1)
As the lower bound of an algorithm does not give any important information, programmers usually don't use it to evaluate an algorithm.  

Most of the time Worst Case Analysis is used to evaluate an algorithm.

In some cases, few algorithms are asymptotically same. For example, Merge Sort.
In all cases, it does ϴ (nLogn) .

Labels:

Comments

Post a Comment