Types of Analysis

Types of Analysis

To analyze the given algorithm, we need to know with which inputs the algorithm takes less time (performing well) and with which inputs the algorithm takes a long time. In general, the first case is called the best case and the second case is called the worst case for the algorithm. To analyze an algorithm, we need some kind of syntax, and that forms the base for asymptotic analysis/notation. There are 3 types of analysis.

1. Best Case  
  • Defines the input for which the algorithm takes the least time (fastest time to complete).
  • Best case of a given algorithm is considered when the resource usage is at least. Usually the resource being considered is running time.
  • The term best case performance is used to describe an algorithm’s behavior under optimal conditions.
  • The best-case complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n.
  • In the best-case analysis, we calculate lower bound on running time of an algorithm.
  • For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list. In sorting problem, the best case occurs when the input elements are already sorted in required order.
2. Worst Case
  • Defines the input for which the algorithm takes the least time (fastest time to complete).
  • Best case of a given algorithm is considered when the resource usage is at least. Usually the resource being considered is running time.
  • The term best case performance is used to describe an algorithm’s behavior under optimal conditions.
  • The best-case complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size n.
  • In the best-case analysis, we calculate lower bound on running time of an algorithm.
  • For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list. In sorting problem, the best case occurs when the input elements are already sorted in required order.
3. Average Case 
  • Average case of a given algorithm is considered when the resource usage is on average.
  • Average performance and worst-case performance are the most used in algorithm analysis.
  • The average-case complexity of the algorithm is the function defined by the average number of steps taken on any instance of size n.
  • In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs.
  • For example, the average case for a simple linear search on a list occurs when the desired element is any element of the list. In sorting problem the average case occurs when the input elements are randomly arranged.

Types of Analysis

Scroll to top