Please enable JavaScript.
Coggle requires JavaScript to display documents.
Fundamentals of the Analysis of Algorithm Efficiency, The Analysis…
-
The Analysis Framework
-
-
-
-
Order of growth
-
The smallest the growing is, the fastest the code will run
As a good example, we have the logarithmic function, that grows so slowly that we expect it to run practically instantaneously on input of all realistic sizes
As a bad example, we have the exponential function 2n and the factorial function n! Both these functions grow so fast that their values become astronomically large even for rather small values of n
"Algorithms that require an exponential number of operations are practical for solving only problems of very small sizes."
Worst-Case, Best-Case, and Average-Case Efficiencies
The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the fastest among all possible inputs of that size
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n, which is an input (or inputs) of size n for which the algorithm runs the longest among all possible inputs of that size
it guarantees that for any instance of size n, the running time will not exceed Cworst(n), its running time on the worst-case inputs
The average-case efficiency seeks to provide the necessary information about an algorithm’s behavior on a “typical” or “random” input
-
-
-
-
-