How.md

How to do algorithm analysis?

Before going to case analysis let's revise linear search, As I am going to explain Case analysis using a linear search algorithm.

What is a linear search?

Linear search is a simple searching algorithm that searches for an element of a list in sequential order. We start at one end and check every element until the desired elements is found.

Example:

# Python 3 implementation of the approach 
# Linearly search x in arr[]
def search(arr, x): 
    for index, value in enumerate(arr): 
        if value == x: 
            return index 
    return -1
 
# Driver Code 
arr = [1, 10, 30, 15] 
x = 30
print(x, "is present at index", 
      search(arr, x))

Output : 30 is present at index 2

---

There are three cases to analyze an algorithm

1. The worst case
2. Average case
3. Best case

Worst Case Analysis:

For linear search, the worst case happens when we search for an element which is not present in the array or present once at the end of the array. From the above example if the 'X' is not present in the array then search() function will compare it with every element in the array one by one. Therefore the worst case time complexity of linear search would be O(n).

Average Case Analysis:

The average case analysis we take the average over all inputs(of the given size). For linear search, we will assume that all cases are uniformly distributed (includes the key(x) not present in the array). We add all the cases and divide the sum by (n+1).

Average Case Time =
= = Θ(n)

This analysis may not be possible for every algorithm. So, rarely we do it. Mostly for the average case, the time complexity we get is similar to the worst case.

Best Case Analysis:

In a linear search, the best case occurs when the key(x) is present at the first index. The no of operations in the best case is constant(1) it doesn't depend on the size of the array. So the time complexity in the best case would be Θ(1)

Bonus

Here's the list of other algorithms

Contributed by Shyam Kumar With 💜.

Reach me on