Analysis Framework

“Analysis of algorithms” mean an investigation of an algorithm’s efficiency with respect to two resources: running time and memory space.
There are two kinds of efficiency:
1. Time efficiency – how fast an algorithm runs.
2. Space efficiency – how much memory an algorithm needs.

Measuring an input’s size

It is logical to investigate an algorithm’s efficiency as a function of some parameter $n$ indicating the algorithm’s input size
Selecting such a parameter is quite straightforward.
For example,
- Sorting – An input size is the size of the list.
- Find the largest element in the list of an array
- Compute the sum of $n$ numbers.

Units for measuring running time is to count the number of times the algorithm’s basic operations is executed.
The basic operation means the operation contributing the most to the total running time.
The basic operation is usually the most time-consuming operation in the algorithm’s innermost loop.
- For example,
  - Sorting – the basic operation is key comparison.

T(n)\approx c_{op}C(n)

$T$ = running time of an algorithm
$n$ = input size
$c_{op}$ = execution time of the basic operation
$C$ = number of times the basic operation is executed
How much longer will the algorithm run if we double its input size?
Assume that $C(n)=\frac{1}{2}n(n-1)=\frac{1}{2}n^2-\frac{1}{2}n\approx\frac{1}{2}n^2$
Therefore, $\frac{T(2n)}{T(n)}\approx\frac{c_{op}C(2n)}{c_{op}C(n)}\approx\frac{\frac{1}{2}(2n)^2}{\frac{1}{2}n^2}=4$
We were able to answer the question without actually knowing the value of $c_{op}$
We concentrate on the count’s order of growth for large-size inputs.

The magnitude of the numbers in the following table has a profound significance for the analysis of algorithms.
Algorithms that require an exponential number of operations are practical for solving only problems of very small size.
Basic asymptotic efficiency classes

There are many algorithms for which running time depends not only on an input size but also on the specifics of a particular input.
The worst-case efficiency of an algorithm is its efficiency for the worst-case input of size $n$ , which is an input of size $n$ for which the algorithm runs the longest among all possible inputs of that size.
The best-case efficiency of an algorithm is its efficiency for the best-case input of size $n$ , which is an input of size $n$ for which the algorithm runs the fastest among all possible inputs of that size.
To analyze the algorithm’s average-case efficiency, we must make some assumptions about possible inputs of size $n$ .