Analysis of Algorithms | Set 2 (Worst, Average and Best Cases) - GeeksforGeeks (2023)

In the previous post, we discussed how Asymptotic analysis overcomes the problems of the naive way of analyzing algorithms. But let’s take an overview of the asymptotic notation and learn about What is Worst, Average, and Best cases of an algorithm:

Popular Notations in Complexity Analysis of Algorithms

1. Big-O Notation

We define an algorithm’s worst-case time complexity by using the Big-O notation, which determines the set of functions grows slower than or at the same rate as the expression. Furthermore, it explains the maximum amount of time an algorithm requires considering all input values.

2. Omega Notation

It defines the best case of an algorithm’s time complexity, the Omega notation defines whether the set of functions will grow faster or at the same rate as the expression. Furthermore, it explains the minimum amount of time an algorithm requires considering all input values.

3. Theta Notation

It defines the average case of an algorithm’s time complexity, the Theta notation defines when the set of functions lies in both O(expression) and Omega(expression), then Theta notation is used. This is how we define a time complexity average case for an algorithm.

Measurement of Complexity of an Algorithm

Based on the above three notations of Time Complexity there are three cases to analyze an algorithm:

1. Worst Case Analysis (Mostly used)

In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x) is not present in the array. When x is not present, the search() function compares it with all the elements of arr[] one by one. Therefore, the worst-case time complexity of the linear search would be O(n).

2. Best Case Analysis (Very Rarely used)

In the best case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case that causes a minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be Ω(1)

3. Average Case Analysis (Rarely used)

In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs. We must know (or predict) the distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in the array). So we sum all the cases and divide the sum by (n+1). Following is the value of average-case time complexity.

Average Case Time = \sum_{i=1}^{n}\frac{\theta (i)}{(n+1)} = \frac{\theta (\frac{(n+1)*(n+2)}{2})}{(n+1)} = \theta (n)

Which Complexity analysis is generally used?

Below is the ranked mention of complexity analysis notation based on popularity:

1. Worst Case Analysis:

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

2. Average Case Analysis

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

3. Best Case Analysis

The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn’t provide any information as in the worst case, an algorithm may take years to run.

Interesting information about asymptotic notations:

A) For some algorithms, all the cases (worst, best, average) are asymptotically the same. i.e., there are no worst and best cases.

  • Example: Merge Sort does Θ(n log(n)) operations in all cases.

B) Where as most of the other sorting algorithms have worst and best cases.

  • Example 1: In the typical implementation of Quick Sort (where pivot is chosen as a corner element), the worst occurs when the input array is already sorted and the best occurs when the pivot elements always divide the array into two halves.
  • Example 2: For insertion sort, the worst case occurs when the array is reverse sorted and the best case occurs when the array is sorted in the same order as output.

Examples with their complexity analysis:

1. Linear search algorithm:

C

// C implementation of the approach

#include <stdio.h>

// Linearly search x in arr[].

// If x is present then return the index,

// otherwise return -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's code*/

int main()

{

int arr[] = { 1, 10, 30, 15 };

int x = 30;

int n = sizeof(arr) / sizeof(arr[0]);

// Function call

printf("%d is present at index %d", x,

search(arr, n, x));

getchar();

return 0;

}

C++

// C++ implementation of the approach

#include <bits/stdc++.h>

using namespace std;

// Linearly search x in arr[].

// If x is present then return the index,

// otherwise return -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's Code

int main()

{

int arr[] = { 1, 10, 30, 15 };

int x = 30;

(Video) Analysis of Algorithms | Set 2 (Worst, Average and Best Cases) | GeeksforGeeks

int n = sizeof(arr) / sizeof(arr[0]);

// Function call

cout << x << " is present at index "

<< search(arr, n, x);

return 0;

}

Java

// Java implementation of the approach

public class GFG {

// Linearly search x in arr[]. If x is present then

// return the index, otherwise return -1

static 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's code*/

public static void main(String[] args)

{

int arr[] = { 1, 10, 30, 15 };

int x = 30;

int n = arr.length;

// Function call

System.out.printf("%d is present at index %d", x,

search(arr, n, x));

}

}

Python3

# Python 3 implementation of the approach

# Linearly search x in arr[]. If x is present

# then return the index, otherwise return -1

def search(arr, x):

for index, value in enumerate(arr):

if value == x:

return index

return -1

# Driver's Code

if __name__ == '__main__':

arr = [1, 10, 30, 15]

x = 30

# Function call

print(x, "is present at index",

search(arr, x))

C#

// C# implementation of the approach

using System;

public class GFG {

// Linearly search x in arr[]. If x is present then

// return the index, otherwise return -1

static 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's code*/

public static void Main()

{

int[] arr = { 1, 10, 30, 15 };

int x = 30;

int n = arr.Length;

// Function call

Console.WriteLine(x + " is present at index "

+ search(arr, n, x));

}

}

(Video) Analysis of Algorithms Set 2 Worst, Average and Best Cases GeeksforGeeks ---

PHP

<?php

// PHP implementation of the approach

// Linearly search x in arr[]. If x

// is present then return the index,

// otherwise return -1

function search($arr, $n, $x)

{

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

{

if ($arr[$i] == $x)

return $i;

}

return -1;

}

// Driver's Code

$arr = array(1, 10, 30, 15);

$x = 30;

$n = sizeof($arr);

// Function call

echo $x . " is present at index ".

search($arr, $n, $x);

Javascript

// javascript implementation of the approach

// Linearly search x in arr. If x is present then

// return the index, otherwise return -1

function search(arr , n , x) {

var i;

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

if (arr[i] == x) {

return i;

}

}

return -1;

}

(Video) 1.11 Best Worst and Average Case Analysis

/* Driver program to test above functions */

var arr = [ 1, 10, 30, 15 ];

var x = 30;

var n = arr.length;

document.write(x+" is present at index "+ search(arr, n, x));

Output

30 is present at index 2

Time Complexity Analysis: (In Big-O notation)

  • Best Case: O(1), This will take place if the element to be searched is on the first index of the given list. So, the number of comparisons, in this case, is 1.
  • Average Case: O(n), This will take place if the element to be searched is on the middle index of the given list.
  • Worst Case: O(n), This will take place if:
    • The element to be searched is on the last index
    • The element to be searched is not present on the list

2. In this example, we will take an array of length (n) and deals with the following cases :

  • If (n) is even then our output will be 0
  • If (n) is odd then our output will be the sum of the elements of the array.

Below is the implementation of the given problem:

C

#Python 3 implementation of the approach

def getsum(arr, n):

if n % 2 == 0: # if (n) is even

return 0

Sum = 0

for i in range(n):

Sum += arr[i]

return Sum # if (n) is odd

#Driver's Code

if __name__ == '__main__':

arr1 = [1,2,3,4] # Declaring an array of even length

n1 = len(arr1)

arr2 = [1,2,3,4,5] # Declaring an array of odd length

n2 = len(arr2)

#Function call

print(getsum(arr1,n1)) # print 0 because (n) is even

print(getsum(arr2,n2)) # print sum of array because (n) is odd

#This code is contributed by Syed Maruf Ali

C++

// C++ implementation of the approach

#include <bits/stdc++.h>

using namespace std;

int getSum(int arr[], int n)

{

if (n % 2 == 0) // (n) is even

{

return 0;

}

int sum = 0;

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

sum += arr[i];

}

return sum; // (n) is odd

}

// Driver's Code

int main()

{

// Declaring two array one of length odd and other of

// length even;

int arr[4] = { 1, 2, 3, 4 };

int a[5] = { 1, 2, 3, 4, 5 };

// Function call

cout << getSum(arr, 4)

<< endl; // print 0 because (n) is even

cout << getSum(a, 5)

<< endl; // print sum because (n) is odd

}

// This code is contributed by Suruchi Kumari

(Video) Data Structures & Algorithms - Complexity Analysis - Best, Average, & Worst Case

Java

// Java implementation of the approach

public class GFG {

static int getsum(int arr[], int n)

{

if (n % 2 == 0) // if (n) is even

{

return 0;

}

int sum = 0;

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

sum += arr[i];

}

return sum; // if (n) is odd

}

/* Driver's code*/

public static void main(String[] args)

{

int arr1[]

= { 1, 2, 3,

4 }; // Declaring an array of even length

int n1 = arr1.length;

int arr2[]

= { 1, 2, 3, 4,

5 }; // Declaring an array of odd length

int n2 = arr2.length;

// Function call

System.out.println(getsum(

arr1, n1)); // print 0 because (n) is even

System.out.println(getsum(

arr2,

n2)); // print sum of array because (n) is odd

}

} // This code is contributed by Syed Maruf Ali (Sdmrf)

Python3

# Python 3 implementation of the approach

def getsum(arr, n):

if n % 2 == 0: # if (n) is even

return 0

Sum = 0

for i in range(n):

Sum += arr[i]

return Sum # if (n) is odd

# Driver's Code

if __name__ == '__main__':

arr1 = [1, 2, 3, 4] # Declaring an array of even length

n1 = len(arr1)

arr2 = [1, 2, 3, 4, 5] # Declaring an array of odd length

n2 = len(arr2)

# Function call

print(getsum(arr1, n1)) # print 0 because (n) is even

print(getsum(arr2, n2)) # print sum of array because (n) is odd

# This code is contributed by Syed Maruf Ali

Output

015

Time Complexity Analysis:

  • Best Case: The order of growth will be constant because in the best case we are assuming that (n) is even.
  • Average Case: In this case, we will assume that even and odd are equally likely, therefore Order of growth will be linear
  • Worst Case: The order of growth will be linear because in this case, we are assuming that (n) is always odd.

For more details, please refer: Design and Analysis of Algorithms. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

RecommendedSolve DSA problems on GfG Practice.Solve Problems

FAQs

What is best case worst case and average case in algorithm? ›

Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n. Average case is the function which performs an average number of steps on input data of n elements.

What is the best average and worst case analysis of binary search algorithm? ›

Binary search algorithm
Visualization of the binary search algorithm where 7 is the target value
ClassSearch algorithm
Worst-case performanceO(log n)
Best-case performanceO(1)
Average performanceO(log n)
2 more rows

What is the best and the 2 worst case scenarios of using a linear search? ›

Analysis. For a list with n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.

Why worst case analysis of algorithms is most important than average case analysis? ›

Since we can seldom guarantee precisely how an algorithm will be exercised, usually we cannot obtain an average-case measurement that is likely to be accurate. The worst case gives us an upper bound on performance. Analyzing an algorithm's worst case guarantees that it will never perform worse than what we determine.

What is worst case analysis of algorithms? ›

In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as n in asymptotic notation). It gives an upper bound on the resources required by the algorithm.

What is the best case and worst-case complexity of bubble sort algorithm? ›

Summary. Bubble Sort is an easy-to-implement, stable sorting algorithm with a time complexity of O(n²) in the average and worst cases – and O(n) in the best case.

What is the best example of best worst most likely case? ›

common thread of conversation. John considers the worst, best and most likely outcome to a scenario that is worrisome to him. John stands in line at the grocery and decides what the best worst and most likely reason is that the woman in front of him. is yelling at her child.

What is best case worst case and average case complexity of a binary search tree? ›

Binary search's average and worst case time complexity is O ( log n ) O(\log n) O(logn), while binary search tree does have an average case of O ( log n ) O(\log n) O(logn), it has a worst case of O ( n ) O(n) O(n).

How do you analyze worst case complexity? ›

1. Big-O Notation. We define an algorithm's worst-case time complexity by using the Big-O notation, which determines the set of functions grows slower than or at the same rate as the expression. Furthermore, it explains the maximum amount of time an algorithm requires considering all input values.

Which searching algorithm is best? ›

The binary search algorithm works on the principle of divide and conquer and it is considered the best searching algorithm because it's faster to run.

What do you mean by best case and worst case time complexity of an algorithm explains in detail? ›

Worst case runtime means that you are feeding the worst possible input (of that size) into your algorithm. Best case runtime means that you are feeding the best possible input into your algorithm. For an input of size n, perhaps the worst case runtime is T(n)=2n2 + 5, and the best case runtime is 3n. Big-O vs.

Which of the following algorithm takes the same time in all three cases example best average and worst? ›

9. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case? Explanation: The time complexity of counting sort remains unvaried in all the three cases. It is given by O(n+k).

What is the importance of average case analysis of algorithms explain? ›

No matter how they are derived, we are interested in average-case results because, in the large number of situations where random input is a reasonable model, an accurate analysis can help us: Compare different algorithms for the same task. Predict time and space requirements for specific applications.

What are the reasons for worst case analysis? ›

Worst-case analysis tries to answer the same questions that statistical analysis does, but rather than varying parameters randomly, you identify what the worst possible values of these parameters may be, and then perform your analysis to see if the system meets its specifications under such circumstances.

Which is the best sorting algorithm based on time complexity? ›

Time Complexities of all Sorting Algorithms
AlgorithmTime Complexity
BestWorst
Insertion SortΩ(n)O(n^2)
Heap SortΩ(n log(n))O(n log(n))
Quick SortΩ(n log(n))O(n^2)
10 more rows
22 Sept 2022

What is average case in algorithm? ›

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

What is worst case efficiency of an algorithm? ›

Worst Case Efficiency - is the maximum number of steps that an algorithm can take for any collection of data values.

Is Big-O the worst case? ›

Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. It provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm.

What is the worst-case for bubble sort? ›

What is the time complexity of quick sort in best case and worst-case? ›

Quicksort's average case time complexity is O(n*logn) . The following is the average-case recurrence. 3). Worst Case Complexity: The worst-case situation is when the partitioning algorithm picks the largest or smallest element as the pivot element every time.

What is the best case and worst case time complexity of bubble sort if we are implementing the optimized bubble sort which uses a flag variable for swapping indication? ›

Worst-Case and Average-Case Time Complexity of Bubble sort algorithm in C is O ( n 2 ) O(n^2) O(n2). Best-Case Time Complexity of Bubble sort algorithm is O(n) where we implement the optimized approach of Bubble sort in C. Space complexity for the standard Bubble sort algorithm in C is O(1).

What is worst and best-case scenario? ›

Your best-case scenario is the best possible financial outcome if everything goes according to plan. Your worst-case scenario is the most unfavorable possible financial outcome for your business. Creating helpful and actionable projections takes time and effort, especially the first time through.

What are the best-case scenarios? ›

If something is described as the best-case scenario, this means that it is what people want to happen and are working to achieve. It can be compared to the worst-case scenario, which would be the worst possible outcome. Many times people will use both of these phrases together.

What is the best example of a best? ›

The best person or thing or the best example - thesaurus
  • ideal. noun. the best example of something that you can think of or imagine.
  • perfection. noun. someone or something that is considered to be the best possible.
  • optimum. noun. ...
  • star. noun. ...
  • the epitome of. phrase. ...
  • paragon. noun. ...
  • king. noun. ...
  • flagship. noun.

What is the worst-case complexity of binary search algorithm? ›

How do you calculate worst case? ›

If the measure of x is time in minutes, or another measure where a high value is undesirable, the “worst case” should be the mean time plus three standard deviations for the process, or (20 + 30 + 60) + 3*10.7 = 110 + 32.1 = 142.1.

How do you calculate worst case run time? ›

To count the worst time, you need to find the maximum number of operations that will be performed. Because you have only a single operation in a double loop, it is enough to find out how many times the inner loop will execute. You can substitute in the second equasion to get j < N .

What is average case in algorithm? ›

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

What is best case complexity of an algorithm? ›

Omega Notation. It defines the best case of an algorithm's time complexity, the Omega notation defines whether the set of functions will grow faster or at the same rate as the expression. Furthermore, it explains the minimum amount of time an algorithm requires considering all input values.

Which algorithm has same complexity in all cases is best worst and average? ›

Merge sort

Best, average and worst case time complexity: nlogn which is independent of distribution of data.

What is the best worst and average case time complexity of merge sort? ›

The list of size N is divided into a max of Logn parts, and the merging of all sublists into a single list takes O(N) time, the worst-case run time of this algorithm is O(nLogn) Best Case Time Complexity: O(n*log n) Worst Case Time Complexity: O(n*log n) Average Time Complexity: O(n*log n) The time complexity of ...

What is worst case efficiency of an algorithm? ›

Worst Case Efficiency - is the maximum number of steps that an algorithm can take for any collection of data values.

Is Big-O the worst case? ›

Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. It provides us with an asymptotic upper bound for the growth rate of the runtime of an algorithm.

How do you find best case algorithm? ›

In the best case analysis, we calculate the lower bound of the execution time of an algorithm. It is necessary to know the case which causes the execution of the minimum number of operations. In the linear search problem, the best case occurs when x is present at the first location.

What is average best and worst case complexity of deletion of a node? ›

The time complexity in this case is O(n). In cases where the node to be deleted is known only by value, the list has to be searched and the time complexity becomes O(n) in both singly- and doubly-linked lists.

What is the best case and worst case complexity of linear search? ›

In linear search, best-case complexity is O(1) where the element is found at the first index. Worst-case complexity is O(n) where the element is found at the last index or element is not present in the array.

What are the worst case and average case complexity of a binary search tree? ›

Binary search's average and worst case time complexity is O ( log n ) O(\log n) O(logn), while binary search tree does have an average case of O ( log n ) O(\log n) O(logn), it has a worst case of O ( n ) O(n) O(n).

What are the average and worst case time complexities of the Quicksort algorithm? ›

The worst case time complexity of a typical implementation of QuickSort is O(n2). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when input array is sorted or reverse sorted and either first or last element is picked as pivot.

Which algorithm is the best sorting method in place with no quadratic worst case scenarios? ›

Answer: Quick Sort is the best algorithm.

Which of the following sorting algorithm can be realized from the worst case complexity? ›

The correct answer is option 1. Concept: Merge-sort algorithm: Merge Sort is a Divide and Conquer algorithm.

Which sorting algorithm has the same time complexity for all the cases worst best and average )? A quick b merge C insertion D selection? ›

Merge sort gives time complexity of O(nlogn) in every case, be it best, average or worst. In merge sort, performance is affected least by the order of input sequence. For selection sort, the best- case and worst-case performance of Selection is O(n2) only.

Which of the following algorithm takes the same time in all three cases best average and worst? ›

9. The complexity of which of the following sorting algorithms remains to be the same in its best, average and worst case? Explanation: The time complexity of counting sort remains unvaried in all the three cases. It is given by O(n+k).

Which of the following algorithms has worst time complexity? ›

Time Complexities of all Sorting Algorithms
AlgorithmTime Complexity
BestWorst
Selection SortΩ(n^2)O(n^2)
Bubble SortΩ(n)O(n^2)
Insertion SortΩ(n)O(n^2)
10 more rows
22 Sept 2022

Videos

1. DSA10e - Best, Worst, Average Case analysis
(EZCSE)
2. 1.7 Worst ,Best ,Average case in analysis of algorithm
(OU Education)
3. An In-Depth Algorithmic Analysis of Bubble Sort. Best Case, Average Case, & Worst Case.
(Back To Back SWE)
4. Best Case, Average Case and Worst Case Time Complexity of an Algorithm | GATECSE | DAA
(THE GATEHUB)
5. C Programming, Worst, Best, and Average Case [Tagalog].
(ProgrammerNgPinas)
6. [Episode #7] Best case, worst case and Average case | Execution Time Cases of Algorithm | DSA
(4T Spotters)
Top Articles
Latest Posts
Article information

Author: Manual Maggio

Last Updated: 02/16/2023

Views: 6045

Rating: 4.9 / 5 (69 voted)

Reviews: 84% of readers found this page helpful

Author information

Name: Manual Maggio

Birthday: 1998-01-20

Address: 359 Kelvin Stream, Lake Eldonview, MT 33517-1242

Phone: +577037762465

Job: Product Hospitality Supervisor

Hobby: Gardening, Web surfing, Video gaming, Amateur radio, Flag Football, Reading, Table tennis

Introduction: My name is Manual Maggio, I am a thankful, tender, adventurous, delightful, fantastic, proud, graceful person who loves writing and wants to share my knowledge and understanding with you.