This article has participated in the Denver Nuggets Creators Camp 3 “More Productive writing” track, see details: Digg project | creators Camp 3 ongoing, “write” personal impact.

In the last article, we discussed how asymptotic analysis can overcome the naive approach of algorithmic analysis. In this article, we will take linear search as an example and analyze it using asymptotic analysis. We can analyze algorithms in three cases:

  1. The worst
  2. On average
  3. The best situation

Let’s consider the following implementation of linear search.

C++ implementation of this method

#include <bits/stdc++.h>
using namespace std;

// Linear search for x in arr[].
// Return index if x exists, otherwise -1
int search(int arr[], int n, int x)
{
	int i;
	for (i = 0; i < n; i++) {
		if (arr[i] == x)
			return i;
	}
	return - 1;
}

// Driver code
int main(a)
{
	int arr[] = { 1.10.30.15 };
	int x = 30;
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << x << " is present at index "
		<< search(arr, n, x);

	getchar(a);return 0;
}
Copy the code

C implementation of this method

#include <stdio.h>

// Linear search for x in arr[].
// Return index if x exists, otherwise -1
int search(int arr[], int n, int x)
{
	int i;
	for (i = 0; i < n; i++) {
		if (arr[i] == x)
			return i;
	}
	return - 1;
}

/* Test the driver for the above function */
int main(a)
{
	int arr[] = { 1.10.30.15 };
	int x = 30;
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("%d is present at index %d", x,
		search(arr, n, x));

	getchar();
	return 0;
}
Copy the code

A Java implementation of this method

public class HY {

	// Linear search for x in arr[].
        // Return index if x exists, otherwise -1
	static int search(int arr[], int n, int x)
	{
		int i;
		for (i = 0; i < n; i++) {
			if (arr[i] == x) {
				returni; }}return -1;
	}

	/* Test the driver for the above function */
	public static void main(String[] args)
	{
		int arr[] = { 1.10.30.15 };
		int x = 30;
		int n = arr.length;
		System.out.printf("%d is present at index %d", x, search(arr, n, x)); }}Copy the code

The Python 3 implementation of this method

// Linear search for x in arr[]. // return index if x exists, otherwise return -1

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))
Copy the code

Output:

30 is present at index 2
Copy the code

Worst-case analysis (usually completed)

In worst-case analysis, we calculate the upper limit of the algorithm’s running time. We need to know what causes the maximum operand to be executed. For linear searches, the worst that can happen is when there is no element in the array to search for (x in the code above). When x does not exist, the search() function compares it one by one with all the elements of arr[]. Thus, the worst-case time complexity of linear search is θ (n).

Average case studies (sometimes completed)

In the averaging case, we take all possible inputs and calculate the computation time for all inputs. Add all the calculated values and divide the sum by the total input. We must know (or predict) the distribution of cases. For the linear search problem, let’s assume that all cases are uniformly distributed (including cases where X is not in the array). So let’s sum up all the cases and divide the sum by n plus 1. Below are the average case time complexity values.

Best Case Study (false)

In the best case study, we calculate the lower bound of the algorithm’s running time. We must know the situation that leads to the fewest operands being performed. In linear search problems, the best case happens when x appears in the first position. The number of operations in the best case is constant (independent of n). So the best-case time complexity is θ (1)

Most of the time, we do worst-case analysis to analyze the algorithm. In the worst-case analysis, we guarantee an upper bound on the running time of the algorithm, which is a good piece of information.

In most practical cases, average case analysis is not easy to do and is rarely done. In average case analysis, we must know (or predict) the mathematical distribution of all possible inputs.

The best case study is fake. Ensuring that the lower limit of the algorithm does not provide any information, because in the worst case, the algorithm may take years to run.

For some algorithms, all cases are asymptotically the same, that is, there are no worst and best cases. For example merge sort. Merge sort performs θ (nLogn) in all cases. Most other sorting algorithms have worst-case and best-case scenarios. For example, in a typical implementation of quicksort (where the pivot is chosen as the corner element), the worst that can happen is when the input array is already sorted, and the best that can happen is when the pivot element always splits the array in half. For insert sort, the worst case occurs when the array is sorted backwards, and the best case occurs when the array is sorted in the same order as the output.

Next, algorithm analysis | 3 groups (asymptotic notation)