2.1- Analysis framework Flashcards
also called time complexity,
indicates how fast an algorithm in question runs.
time efficiency
also called space
complexity, refers to the amount of memory units required by the algorithm in addition to the space needed for its input and output.
space efficiency
it is preferable to measure size by the number b of bits in
the n’s binary representation:
b = [log{2} n] + 1
This metric usually gives a better idea about the efficiency of algorithms in question.
One possible approach is to count the number of times each of the algorithm’s
operations is executed. This approach is both excessively difficult and, as we
shall see, usually unnecessary. The thing to do is to identify the most important
operation of the algorithm, called the ____ _____, the operation contributing the most to the total running time, and compute the number of times the basic operation is executed.
basic operation
it is not difficult to identify the basic operation of an algorithm: it
is usually the most time-consuming operation in the algorithm’s innermost loop.
For example, most sorting algorithms work by comparing elements (keys) of a list being sorted with each other; for such algorithms, the basic operation is a key comparison
the established framework for the analysis of an algorithm’s ____ _____ suggests measuring it by counting the number of times the algorithm’s basic operation is executed on inputs of size n.
time efficiency
_____ function 2^n and the
factorial function n! Both these functions grow so fast that their values become
astronomically large even for rather small values of n.
exponential
There is a tremendous difference between
the orders of growth of the functions 2^n and n!, yet both are often referred to as “exponential-growth functions” (or simply “exponential”) despite the fact that, strictly speaking, only the former should be referred to as such. The bottom line,
which is important to remember, is this:
Algorithms that require an exponential number of operations are practical
for solving only problems of very small sizes.
The ___-___ ____ 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. The way to determine
the worst-case efficiency of an algorithm is, in principle, quite straightforward:
analyze the algorithm to see what kind of inputs yield the largest value of the basic
operation’s count C(n) among all possible inputs of size n and then compute this
worst-case value C{worst}(n).
worst-case efficiency
The___-___ ____ 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. Accordingly, we can analyze the bestcase efficiency as follows. First, we determine the kind of inputs for which the count
C(n) will be the smallest among all possible inputs of size n. (Note that the best
case does not mean the smallest input; it means the input of size n for which the
algorithm runs the fastest.) Then we ascertain the value of C(n) on these most
convenient inputs. For example, the best-case inputs for sequential search are lists
of size n with their first element equal to a search key; accordingly, C{best}(n) = 1
for this algorithm.
best-case efficiency
The analysis of the best-case efficiency is not nearly as important as that
of the worst-case efficiency. But it is not completely useless, either.
neither the worst-case
analysis nor its best-case counterpart yields the necessary information about an
algorithm’s behavior on a “typical” or “random” input. This is the information that
the average-case efficiency seeks to provide. To analyze the algorithm’s ___-____ _____, we must make some assumptions about possible inputs of size n.
average-case efficiency
It applies not to
a single run of an algorithm but rather to a sequence of operations performed
on the same data structure. It turns out that in some situations a single operation
can be expensive, but the total time for an entire sequence of n such operations is
always significantly better than the worst-case efficiency of that single operation
multiplied by n. So we can “amortize” the high cost of such a worst-case occurrence over the entire sequence in a manner similar to the way a business would
amortize the cost of an expensive item over the years of the item’s productive life.
amortized efficiency
Both time and space efficiencies are measured as functions of the algorithm’s _____ size.
input
____ _____ is measured by counting the number of times the algorithm’s
basic operation is executed. Space efficiency is measured by counting the
number of extra memory units consumed by the algorithm.
Time efficiency
The efficiencies of some algorithms may differ significantly for inputs of the same ____. For such algorithms, we need to distinguish between the worst-case, ___-____, and best-case efficiencies.
size
average-case
