In fact, there are two kinds of algorithm efficiency: time efficiency, indicating how fast the algorithm runs, and space ef-ficiency, indicating how much extra memory it uses.

**Analyzing an Algorithm**

We usually want our algorithms to possess
several qualities. After correctness, by far the most important is ** efficiency**.
In fact, there are two kinds of algorithm efficiency:

Another desirable characteristic of an
algorithm is ** simplicity**. Unlike effi-ciency, which can be precisely defined
and investigated with mathematical rigor, simplicity, like beauty, is to a
considerable degree in the eye of the beholder. For example, most people would
agree that Euclid’s algorithm is simpler than the middle-school procedure for
computing gcd

Yet another desirable characteristic of an
algorithm is ** generality**. There are, in fact, two issues here: generality of
the problem the algorithm solves and the set of inputs it accepts. On the first
issue, note that it is sometimes easier to design an algorithm for a problem
posed in more general terms. Consider, for example, the problem of determining
whether two integers are relatively prime, i.e., whether their only common
divisor is equal to 1. It is easier to design an algorithm for a more general
problem of computing the greatest common divisor of two integers and, to solve
the former problem, check whether the gcd is 1 or not. There are situations,
however, where designing a more general algorithm is unnecessary or difficult
or even impossible. For example, it is unnecessary to sort a list of

As to the set of inputs, your main concern
should be designing an algorithm that can handle a set of inputs that is
natural for the problem at hand. For example, excluding integers equal to 1 as
possible inputs for a greatest common divisor algorithm would be quite
unnatural. On the other hand, although the standard formula for the roots of a
quadratic equation holds for complex coefficients, we would normally not
implement it on this level of generality unless this capability is explicitly
required.

If you are not satisfied with the algorithm’s
efficiency, simplicity, or generality, you must return to the drawing board and
redesign the algorithm. In fact, even if your evaluation is positive, it is
still worth searching for other algorithmic solutions. Recall the three
different algorithms in the previous section for computing the greatest common
divisor: generally, you should not expect to get the best algorithm on the
first try. At the very least, you should try to fine-tune the algorithm you
already have. For example, we made several improvements in our implementation
of the sieve of Eratosthenes compared with its initial outline in Section 1.1.
(Can you identify them?) You will do well if you keep in mind the following
observation of Antoine de Saint-Exupery,´ the French writer, pilot, and
aircraft designer: “A designer knows he has arrived at perfection not when
there is no longer anything to add, but when there is no longer anything to
take away.”^{1}

^{}

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

Introduction to the Design and Analysis of Algorithms : Analyzing an Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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