Algorithm - (Case|problem) analysis

Sorting Quicksort Anim

About

Type of case problem in algorithm.

Type

Average

“Average case” analysis is the calculation of the average running time of an algorithm under some assumption (ie about the relative frequencies (distribution) of different inputs that defines (domain|data) knowledge about the problem)

Example:

  • Assuming that every possible input array is equally unlikely, and then analyze the average running time of an algorithm.
  • Using a set of pre-specified benchmarks. Benchmarks data set are known data set:
    • where men agrees up front about some set.
    • that represent practical or typical inputs

Worst

In worst-case analysis, by definition you're making absolutely no assumptions about where the input comes from beyond what the input length N was.

Worst case analysis is usually mathematically much more attractable than trying to analyze the average performance of an algorithm under some distribution over inputs.

Worst case is then usually easier to analyze than the average case.





Discover More
Sorting Quicksort Anim
Algorithm - (Guiding Principle|Guide Line)

Algorithm guiding principle: Worst case analysis asymptotic analysis (won't worry small constant factors or lower order terms)
Sorting Quicksort Anim
Algorithm - Problem

A problem in algorithm is what need to be solved. Problems that cannot be solved by computation are called undecidable Problems that can be solved by computer are called decidable Tractable:...



Share this page:
Follow us:
Task Runner