In this section, we systematically apply the general framework outlined in Section 2.1 to analyzing the time efficiency of nonrecursive algorithms.

**Mathematical
Analysis of Non recursive Algorithms**

In this section, we systematically apply the
general framework outlined in Section 2.1 to analyzing the time efficiency of
nonrecursive algorithms. Let us start with a very simple example that
demonstrates all the principal steps typically taken in analyzing such
algorithms.

**EXAMPLE 1 **Consider
the problem of finding the value of the largest element** **in a list
of ** n** numbers. For simplicity, we
assume that the list is implemented as an array. The following is pseudocode of
a standard algorithm for solving the problem.

**ALGORITHM** *MaxElement*** (A**[0

//Determines the value of the largest element in a given array

//Input: An array ** A**[0

//Output:
The value of the largest element in *A*** maxval **←

**for ***i*** **←** **1** to ***n*** **−** **1** do**

**if **** A**[

**return ***maxval*

The
obvious measure of an input’s size here is the number of elements in the array,
i.e., ** n.** The operations that are going to
be executed most often are in the algorithm’s

Let us
denote ** C(n)** the number of times this
comparison is executed and try to find a formula expressing it as a function of
size

** n** − 1 times.
Thus,

Here is a
general plan to follow in analyzing nonrecursive algorithms.

**General
Plan for Analyzing the Time Efficiency of Nonrecursive Algorithms**

Decide on
a parameter (or parameters) indicating an input’s size.

Identify
the algorithm’s basic operation. (As a rule, it is located in the inner-most
loop.)

Check
whether the number of times the basic operation is executed depends only on the
size of an input. If it also depends on some additional property, the
worst-case, average-case, and, if necessary, best-case efficiencies have to be
investigated separately.

Set up a
sum expressing the number of times the algorithm’s basic operation is executed.

Using
standard formulas and rules of sum manipulation, either find a closed-form
formula for the count or, at the very least, establish its order of growth.

Before
proceeding with further examples, you may want to review Appen-dix A, which
contains a list of summation formulas and rules that are often useful in
analysis of algorithms. In particular, we use especially frequently two basic
rules of sum manipulation

**EXAMPLE 2 **Consider
the**
**** element
uniqueness problem**: check whether all the

**ALGORITHM** *UniqueElements*** (A**[0

//Determines
whether all the elements in a given array are distinct //Input: An array ** A**[0

//Output:
Returns “true” if all the elements in ** A** are
distinct // and “false” otherwise

**for ***i*** **←** **0** to ***n*** **−** **2** do**

**for ***j*** **←** ***i*** **+** **1** to ***n*** **−** **1** do**

**if **** A**[

The
natural measure of the input’s size here is again ** n,** the
number of elements in the array. Since the innermost loop contains a single
operation (the comparison of two elements), we should consider it as the
algorithm’s basic operation. Note, however, that the number of element
comparisons depends not only on

By
definition, the worst case input is an array for which the number of element comparisons
*C*_{worst}** (n)** is the largest among all arrays
of size

where the
last equality is obtained by applying summation formula (S2). Note that this
result was perfectly predictable: in the worst case, the algorithm needs to
compare all ** n(n** − 1

**EXAMPLE 3 **Given two** n **×

We
measure an input’s size by matrix order ** n**. There
are two arithmetical operations in the innermost loop here—multiplication and
addition—that, in principle, can compete for designation as the algorithm’s
basic operation. Actually, we do not have to choose between them, because on
each repetition of the innermost loop each of the two is executed exactly once.
So by counting one we automatically count the other. Still, following a
well-established tradition, we consider multiplication as the basic operation
(see Section 2.1). Let us set up a sum for the total number of multiplications

Obviously,
there is just one multiplication executed on each repetition of the algorithm’s
innermost loop, which is governed by the variable ** k** ranging
from the lower bound 0 to the upper bound

This
example is simple enough so that we could get this result without all the
summation machinations. How? The algorithm computes *n*^{2} elements
of the product matrix. Each of the product’s elements is computed as the scalar
(dot) product of an ** n**-element
row of the first matrix and an

If we now
want to estimate the running time of the algorithm on a particular machine, we
can do it by the product

where ** c_{m}** is the
time of one multiplication on the machine in question. We would get a more
accurate estimate if we took into account the time spent on the additions, too:

where ** c_{a}** is the
time of one addition. Note that the estimates differ only by their
multiplicative constants and not by their order of growth.

You
should not have the erroneous impression that the plan outlined above always
succeeds in analyzing a nonrecursive algorithm. An irregular change in a loop
variable, a sum too complicated to analyze, and the difficulties intrinsic to
the average case analysis are just some of the obstacles that can prove to be
insur-mountable. These caveats notwithstanding, the plan does work for many
simple nonrecursive algorithms, as you will see throughout the subsequent
chapters of the book.

As a last
example, let us consider an algorithm in which the loop’s variable changes in a
different manner from that of the previous examples.

**EXAMPLE 4 **The
following algorithm finds the number of binary digits in the** **binary
representation of a positive decimal integer.

**ALGORITHM** *Binary**(n)*

//Input:
A positive decimal integer *n*

//Output:
The number of binary digits in ** n**’s binary
representation

**while ***n
>*** **1** do**

** count **←

**return ***count*

First,
notice that the most frequently executed operation here is not inside the **while **loop but rather the comparison** ***n
>*** **1 that
determines whether the loop’s** **body
will be executed. Since the number of times the comparison will be executed is
larger than the number of repetitions of the loop’s body by exactly 1, the
choice is not that important.

A more
significant feature of this example is the fact that the loop variable takes on
only a few values between its lower and upper limits; therefore, we have to use
an alternative way of computing the number of times the loop is executed. Since
the value of ** n** is about halved on each
repetition of the loop, the answer should be about log

Find and
compare the number of divisions, multiplications, and additions/ subtractions
(additions and subtractions are usually bunched together) that are required for
computing the variance according to each of these formulas.

**4. **Consider the following algorithm.

**ALGORITHM** *Mystery**(n)*

*n**S*

**return ***S*

What is
its basic operation?

How many
times is the basic operation executed?

What is
the efficiency class of this algorithm?

Suggest
an improvement, or a better algorithm altogether, and indicate its efficiency class.
If you cannot do it, try to prove that, in fact, it cannot be done.

**5. **Consider the following algorithm.

**ALGORITHM** *Secret*** (A**[0

//Input:
An array ** A**[0

**for ***i*** **←** **1** to ***n*** **−** **1** do**

**if **** A**[

**if **** A**[

**return ***maxval*** **−** ***minval*

Answer
questions (a)–(e) of Problem 4 about this algorithm.

**6. **Consider the following algorithm.

**ALGORITHM** *Enigma*** (A**[0

//Input:
A matrix ** A**[0

**for ***j*** **←** ***i*** **+** **1** to ***n*** **−** **1** do if **** A**[

**return false**

**return true**

Answer
questions (a)–(e) of Problem 4 about this algorithm.

Improve the
implementation of the matrix multiplication algorithm (see Ex-ample 3) by
reducing the number of additions made by the algorithm. What effect will this
change have on the algorithm’s efficiency?

Determine the asymptotic
order of growth for the total number of times all the doors are toggled in the
locker doors puzzle (Problem 12 in Exercises 1.1).

9 Prove the
formula

either by
mathematical induction or by following the insight of a 10-year-old school boy
named Carl Friedrich Gauss (1777–1855) who grew up to become one of the
greatest mathematicians of all times.

10.Mental
arithmetic A 10×10 table is filled with repeating numbers on its diagonals as
shown below. Calculate the total sum of the table’s numbers in your head (after
[Cra07, Question 1.33]).

Consider the following
version of an important algorithm that we will study later in the book.

**ALGORITHM** *GE*** (A**[0

//Input:
An ** n** ×

**for ***j*** **←** ***i*** **+** **1** to ***n*** **−** **1** do for ***k*** **←** ***i*** to ***n*** do**

** A**[

Find the time efficiency class of this algorithm.

What glaring inefficiency does this pseudocode contain and how can it be eliminated to speed the algorithm up?

12. von Neumann’s neighborhood Consider the algorithm that starts with a single square and on each of its n iterations adds new squares all around the outside. How many one-by-one squares are there after n iterations? [Gar99] (In the parlance of cellular automata theory, the answer is the number of cells in the von Neumann neighborhood of range n.) The results for n = 0, 1, and 2 are illustrated below.

13. Page numbering Find the total number of decimal digits needed for num-bering pages in a book of 1000 pages. Assume that the pages are numbered consecutively starting with 1.

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 : Mathematical Analysis of Non recursive Algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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