1. Measuring an Input’s Size
2. Units for Measuring Running Time
3. Orders of Growth
4. Worst-Case, Best-Case, and Average-Case Efficiencies
5. Recapitulation of the Analysis Framework

**The
Analysis Framework**

*1. Measuring an Input’s Size*

*2. Units for Measuring Running Time*

*3. Orders of Growth*

*4. Worst-Case, Best-Case, and Average-Case
Efficiencies*

*5. Recapitulation of the Analysis Framework*

In this
section, we outline a general framework for analyzing the efficiency of
algo-rithms. We already mentioned in Section 1.2 that there are two kinds of
efficiency: time efficiency and space efficiency. ** Time efficiency**, also
called

**Measuring
an Input’s Size**

Let’s
start with the obvious observation that almost all algorithms run longer on
larger inputs. For example, it takes longer to sort larger arrays, multiply
larger matrices, and so on. Therefore, it is logical to investigate an
algorithm’s efficiency as a function of some parameter ** n** indicating the algorithm’s input
size.

There are
situations, of course, where the choice of a parameter indicating an input size
does matter. One such example is computing the product of two ** n **×

The
choice of an appropriate size metric can be influenced by operations of the
algorithm in question. For example, how should we measure an input’s size for a
spell-checking algorithm? If the algorithm examines individual characters of
its input, we should measure the size by the number of characters; if it works
by processing words, we should count their number in the input.

We should
make a special note about measuring input size for algorithms solving problems
such as checking primality of a positive integer ** n**. Here,
the input is just one number, and it is this number’s magnitude that determines
the input size. In such situations, it is preferable to measure size by the
number

This
metric usually gives a better idea about the efficiency of algorithms in
question.

**Units for
Measuring Running Time**

The next
issue concerns units for measuring an algorithm’s running time. Of course, we
can simply use some standard unit of time measurement—a second, or millisecond,
and so on—to measure the running time of a program implement-ing the algorithm.
There are obvious drawbacks to such an approach, however: dependence on the
speed of a particular computer, dependence on the quality of a program
implementing the algorithm and of the compiler used in generating the machine
code, and the difficulty of clocking the actual running time of the pro-gram.
Since we are after a measure of an *algorithm*’s
efficiency, we would like to have a metric that does not depend on these
extraneous factors.

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 ** basic operation**, the operation
contributing the most to the total running time, and compute the number of
times the basic operation is executed.

As a
rule, 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. As another example, algorithms for mathematical problems
typically involve some or all of the four arithmetical operations: addition,
subtraction, multiplication, and division. Of the four, the most time-consuming
operation is division, followed by multiplication and then addition and
subtraction, with the last two usually considered together.^{2}

Thus, the
established framework for the analysis of an algorithm’s time ef-ficiency suggests
measuring it by counting the number of times the algorithm’s basic operation is
executed on inputs of size ** n**. We will
find out how to compute such a count for nonrecursive and recursive algorithms
in Sections 2.3 and 2.4, respectively.

Here is
an important application. Let ** c_{op}** be the
execution time of an algo-rithm’s basic operation on a particular computer, and
let

** T (n) **≈

Of
course, this formula should be used with caution. The count ** C(n)** does not contain any information
about operations that are not basic, and, in fact, the count itself is often
computed only approximately. Further, the constant

Note that
we were able to answer the last question without actually knowing the value of ** c_{op}**: it was
neatly cancelled out in the ratio. Also note that

**Orders of
Growth**

Why this
emphasis on the count’s order of growth for large input sizes? A differ-ence in
running times on small inputs is not what really distinguishes efficient
algorithms from inefficient ones. When we have to compute, for example, the
greatest common divisor of two small numbers, it is not immediately clear how
much more efficient Euclid’s algorithm is compared to the other two algorithms
discussed in Section 1.1 or even why we should care which of them is faster and
by how much. It is only when we have to find the greatest common divisor of two
large numbers that the difference in algorithm efficiencies becomes both clear
and important. For large values of ** n**, it is
the function’s order of growth that counts: just look at Table 2.1, which
contains values of a few functions particularly important for analysis of
algorithms.

The
magnitude of the numbers in Table 2.1 has a profound significance for the
analysis of algorithms. The function growing the slowest among these is the
logarithmic function. It grows so slowly, in fact, that we should expect a
program

implementing
an algorithm with a logarithmic basic-operation count to run practi-cally
instantaneously on inputs of all realistic sizes. Also note that although
specific values of such a count depend, of course, on the logarithm’s base, the
formula

log_{a}** n** = log

makes it
possible to switch from one base to another, leaving the count logarithmic but
with a new multiplicative constant. This is why we omit a logarithm’s base and
write simply log ** n** in
situations where we are interested just in a function’s order of growth to
within a multiplicative constant.

On the
other end of the spectrum are the exponential function 2**^{n}** and the factorial function

Algorithms
that require an exponential number of operations are practical for solving only
problems of very small sizes.

Another
way to appreciate the qualitative difference among the orders of growth of the
functions in Table 2.1 is to consider how they react to, say, a twofold
increase in the value of their argument ** n**. The
function log

**Worst-Case,
Best-Case, and Average-Case Efficiencies**

In the
beginning of this section, we established that it is reasonable to measure an
algorithm’s efficiency as a function of a parameter indicating the size of the
algorithm’s input. But there are many algorithms for which running time depends
not only on an input size but also on the specifics of a particular input.
Consider, as an example, sequential search. This is a straightforward algorithm
that searches for a given item (some search key ** K**) in a
list of

**ALGORITHM**

*SequentialSearch*** (A**[0

//Searches
for a given value in a given array by sequential search //Input: An array ** A**[0

//Output:
The index of the first element in ** A** that
matches

or −1 if
there are no matching elements

** i **←

**while ***i
< n*** and **** A**[

**if ***i < n*** return ***i*** else return **−1

Clearly,
the running time of this algorithm can be quite different for the same list
size ** n**. In the worst case, when there
are no matching elements or the first matching element happens to be the last
one on the list, the algorithm makes the largest number of key comparisons
among all possible inputs of size

** n**:

The ** worst-case
efficiency** of an algorithm is its efficiency for the worst-case input
of size

worst-case
value *C _{worst}*

this
chapter.) Clearly, the worst-case analysis provides very important information
about an algorithm’s efficiency by bounding its running time from above. In
other words, it guarantees that for any instance of size ** n**, the running time will not
exceed

** C_{worst} (n), **its
running time on the worst-case inputs.

The ** best-case
efficiency** of an algorithm is its efficiency for the best-case input of
size

of size ** n** with their first element equal
to a search key; accordingly,

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. Though we should
not expect to get best-case inputs, we might be able to take advantage of the
fact that for some algorithms a good best-case performance extends to some
useful types of inputs close to being the best-case ones. For example, there is
a sorting algorithm (insertion sort) for which the best-case inputs are already
sorted arrays on which the algorithm works very fast. Moreover, the best-case
efficiency deteriorates only slightly for almost-sorted arrays. Therefore, such
an algorithm might well be the method of choice for applications dealing with
almost-sorted arrays. And, of course, if the best-case efficiency of an
algorithm is unsatisfactory, we can immediately discard it without further
analysis.

It should
be clear from our discussion, however, that 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 average-case
efficiency, we must make some assumptions about possible inputs of size

Let’s
consider again sequential search. The standard assumptions are that

(a) the
probability of a successful search is equal to ** p** (0 ≤

This
general formula yields some quite reasonable answers. For example, if ** p** = 1 (the
search must be successful), the average number of key comparisons made by
sequential search is

As you
can see from this very elementary example, investigation of the average-case
efficiency is considerably more difficult than investigation of the worst-case
and best-case efficiencies. The direct approach for doing this involves
dividing all instances of size ** n** into
several classes so that for each instance of the class the number of times the
algorithm’s basic operation is executed is the same. (What were these classes
for sequential search?) Then a probability distribution of inputs is obtained
or assumed so that the expected value of the basic operation’s count can be
found.

The
technical implementation of this plan is rarely easy, however, and prob-abilistic
assumptions underlying it in each particular case are usually difficult to
verify. Given our quest for simplicity, we will mostly quote known results
about the average-case efficiency of algorithms under discussion. If you are
interested in derivations of these results, consult such books as [Baa00],
[Sed96], [KnuI], [KnuII], and [KnuIII].

It should
be clear from the preceding discussion that the average-case ef-ficiency cannot
be obtained by taking the average of the worst-case and the best-case efficiencies.
Even though this average does occasionally coincide with the average-case cost,
it is not a legitimate way of performing the average-case analysis.

Does one
really need the average-case efficiency information? The answer is
unequivocally yes: there are many important algorithms for which the
average-case efficiency is much better than the overly pessimistic worst-case
efficiency would lead us to believe. So, without the average-case analysis,
computer scientists could have missed many important algorithms.

Yet
another type of efficiency is called ** amortized 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

**Recapitulation
of the Analysis Framework**

Before we
leave this section, let us summarize the main points of the framework outlined
above.

Both time
and space efficiencies are measured as functions of the algorithm’s input size.

Time
efficiency 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.

The
efficiencies of some algorithms may differ significantly for inputs of the same
size. For such algorithms, we need to distinguish between the worst-case,
average-case, and best-case efficiencies.

The
framework’s primary interest lies in the order of growth of the algorithm’s
running time (extra memory units consumed) as its input size goes to infinity.

In the
next section, we look at formal means to investigate orders of growth. In
Sections 2.3 and 2.4, we discuss particular methods for investigating
nonrecursive and recursive algorithms, respectively. It is there that you will
see how the analysis framework outlined here can be applied to investigating
the efficiency of specific algorithms. You will encounter many more examples
throughout the rest of the book.

**Exercises 2.1**

**
**For each of the following algorithms, indicate (i)
a natural size metric for its inputs, (ii) its basic operation, and (iii)
whether the basic operation count can be different for inputs of the same size:

**
**computing the sum of ** n** numbers

**
**computing ** n**!

**
**finding the largest element in a list of ** n** numbers

**
**Euclid’s algorithm

**
**sieve of Eratosthenes

**
**pen-and-pencil algorithm for multiplying two ** n**-digit decimal integers

**
****a. **Consider
the definition-based algorithm for adding two** ***n*** **×** ***n*** **matrices.** **What is its basic operation? How many
times is it performed as a function of the matrix order ** n**? As a function of the total
number of elements in the input matrices?

**
**Answer the same questions for the definition-based algorithm
for matrix multiplication.

**
**Consider a variation of sequential search that
scans a list to return the number of occurrences of a given search key in the
list. Does its efficiency differ from the efficiency of classic sequential
search?

**
****a. ***Glove selection*** **There are
22 gloves in a drawer: 5 pairs of red gloves, 4** **pairs of yellow, and 2 pairs of green. You select the gloves in
the dark and can check them only after a selection has been made. What is the
smallest number of gloves you need to select to have at least one matching pair
in the best case? In the worst case?

**
***Missing
socks *Imagine that after washing 5 distinct pairs of socks, you* *discover that two socks are missing. Of
course, you would like to have the largest number of complete pairs remaining.
Thus, you are left with 4 complete pairs in the best-case scenario and with 3
complete pairs in the worst case. Assuming that the probability of
disappearance for each of the 10 socks is the same, find the probability of the
best-case scenario; the probability of the worst-case scenario; the number of
pairs you should expect in the average case.

**
****a. **Prove
formula (2.1) for the number of bits in the binary representation of** **a positive decimal integer.

**
**Prove the alternative formula for the number of
bits in the binary repre-sentation of a positive integer ** n**:

** b **=

**c. **What
would be the analogous formulas for the number of decimal digits?

**d.** Explain
why, within the accepted analysis framework, it does not matter whether we use
binary or decimal digits in measuring ** n**’s size.

**6.** Suggest
how any sorting algorithm can be augmented in a way to make the best-case count
of its key comparisons equal to just ** n** − 1 (

**7.** Gaussian
elimination, the classic algorithm for solving systems of ** n** linear equations in

**a.** How
much longer should you expect Gaussian elimination to work on a system of 1000
equations versus a system of 500 equations?

**b.** You
are considering buying a computer that is 1000 times faster than the one you currently
have. By what factor will the faster computer increase the sizes of systems
solvable in the same amount of time as on the old computer?

8. For
each of the following functions, indicate how much the function’s value will
change if its argument is increased fourfold.

9. For
each of the following pairs of functions, indicate whether the first function
of each of the following pairs has a lower, same, or higher order of growth (to
within a constant multiple) than the second function.

**10. ***Invention
of chess*

According
to a well-known legend, the game of chess was invented many centuries ago in
northwestern India by a certain sage. When he took his invention to his king,
the king liked the game so much that he offered the inventor any reward he
wanted. The inventor asked for some grain to be obtained as follows: just a
single grain of wheat was to be placed on the first square of the chessboard,
two on the second, four on the third, eight on the fourth, and so on, until all
64 squares had been filled. If it took just 1 second to count each grain, how
long would it take to count all the grain due to him?

How long
would it take if instead of doubling the number of grains for each square of
the chessboard, the inventor asked for adding two grains?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Fundamentals of the Analysis of Algorithm Efficiency : The Analysis Framework |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.