ADA module-1

MODULE I

INTRODUCTION

Contents

1. Introduction
1. 1. What is an Algorithm?
1. 2. Algorithm Specification
1. 3. Analysis Framework
2. Performance Analysis
2. 1. Space complexity
2. 2. Time complexity
3. Asymptotic Notations
3. 1. Big-Oh notation
3. 2. Omega notation
3. 3. Theta notation
3. 4. Little-oh notation
4. Mathematical analysis of Non-Recursive Algorithms
5. Mathematical analysis of Recursive Algorithms

Dept of CSE-CY Page 1

ADA module-1

1. INTRODUCTION
1.1 What is an Algorithm?
Informal Definition:
An Algorithm is any well-defined computational procedure that takes some value
or set of values as input and produces a set of values or some value as output. Thus
algorithm is a sequence of computational steps that transforms the input into the
output.
Formal Definition:
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for
obtaining a required output for any legitimate input in a finite amount of time.
This definition can be illustrated by a simple diagram:

• The reference to ―instructions‖ in the definition implies that there is

something or
someone capable of understanding and following the instructions given.
• Human beings and the computers nowadays are electronic devices being
involved in performing numeric calculations.
• However, that although the majority of algor ithms are indeed intended for
eventual computer implementation, the notion of algorithm does not depend on
such an assumption.
In addition, all algorithms should satisfy the following criteria or properties.
→
1. INPUT Zero or more quantities are externally supplied.
→
2. OUTPUT At l east one quantity is produced.
→
3. DEFINITENES S Each instruction is clear and unambiguous.
→
4. FINITENESS If we trace out the instructions of an algorithm, then for all cases,
the algorithm terminates after a finite number of steps.
→
5. EFFECTIVENESS Every instruction must very basic so that it can be carried out,
in principle, by a person using only pencil & paper.

Dept of CSE-CY Page 2

ADA module-1

Fundamentals Of Algorithmic Problem Solving

• Algorithms are procedural solutions to problems. These solutions are not answers
but specific instructions for getting answers.
• he following diagram briefly illustrates the sequence of steps one typically goes
through in designing and analyzing an algorithm.
• It includes the following sequence of steps:
✓
Understanding the problem
✓
Deciding on: Computational means, Exact vs. approximate problem
solving, data structure(s), Algorithm design techniques.
✓ Design an algorithm
✓
Prove correctness Analyze the algorithm

• Understanding the problem

✓
Before designing an algorithm the most important thing is to understand the
problem given.
✓ Asking questions, doing a few examples by hand, thinking about special cases,etc.
✓
An Input to an algorithm specifies an instance of the problem the algorithm that it solves.

✓
Important to specify exactly the range of instances the algorithm needs to
handle. Else it

will work correctly for majority of inputs but crash on some ―boundary‖ value.

✓
A correct algorithm is not one that works most of the time, but one that works
correctly for all legitimate inputs.
• Ascertaining the capabilities of a computational device
✓
After understanding need to ascertain the capabilities of the device.
✓
The vast majority of algorithms in use today are still destined to be
programmed for a computer closely resembling the von Neumann machine—a
computer architecture.
✓
Von Neumann architectures are sequential and the algorithms implemented on

Dept of CSE-CY Page 3

ADA module-1
them are called sequential algorithms.
✓
Algorithms which designed to be executed on parallel computers called parallel
algorithms.
✓
For very complex algorithms concentrate on a machine with high speed and
more memory where time is critical.
• Choosing between exact and approximate problem solving
✓
For exact result->exact algorithm
✓
For approximate result->approximation algorithm.
✓
Examples of exact algorithms: Obtaining square roots for numbers and solving non-

linear equations.
✓
An approximation algorithm can be a part of a more sophisticated algorithm

that solves a problem exactly.

• Deciding on appropriate data structures
✓
Algorithms may or may not demand ingenuity in representing their inputs.
✓
Inputs are represented using various data structures.
✓
Algorithm + data structures=program.

• Algorithm Design Techniques and Methods of Specifying an Algorithm

✓
An algorithm design technique (or ―strategy‖ or ―paradigm‖) is a general
approach to solving problems algorithmically that is applicable to a variety of
problems from different areas of computing.
✓
The different algorithm design techniques are: brute force approach, divide and
conquer, greedy method, decrease and conquer, dynamic programming,
transform and conquer and back tracking.
✓ Methods of specifying an algorithm: Using natural language, in this method
ambiguity problem will be there.
✓ The next 2 options are : pseudo code and flowchart.
✓
Pseudo code: mix of natural and programming language. More precise than NL
✓
Flow chart: method of expressing an algorithm by collection of connected
geometric shapes containing descriptions of the algorithm‘s steps.
✓ This representation technique has proved to be inconvenient for large
problems.

Dept of CSE-CY Page 4

ADA module-1
✓
The state of the art of computing has not yet reached a point where an algorithm‘s

description—be it in a natural language or pseudo code—can be fed into an

electronic computer directly. Instead, it needs to be converted into a computer
program written in a particular computer language.
✓
Hence program as yet another way of specifying the algorithm, although it is
preferable to consider it as the algorithm‘s implementation.
• Proving an Algorithm’s Correctness
✓
After specifying an algorithm we have to prove its correctness.
✓
The correctness is to prove that the algorithm yields a required result for every
legitimate input in a finite amount of time.
✓
For example, the correctness of Euclid‘s algorithm for computing the greatest
common divisor stems from the correctness of the equality gcd(m, n) = gcd(n,
m mod n), the simple observation that the second integer gets smaller on every
iteration of the algorithm, and the fact that the algorithm stops when the second
integer becomes 0.
✓
For some algorithms, a proof of correctness is quite easy; for others, it can be
quite complex.
✓ A common technique for proving correctness is to use mathematical induction.
✓
Proof by mathematical induction is most appropriate for proving the correctness
of an algorithm.
• Analyzing an algorithm
✓
After correctness, efficiency has to be estimated.
➢
Time efficiency and space efficiency.
➢
Time: how fast the algorithm runs?
➢
Space: how much extra memory the algorithm needs?
✓
Simplicity: how simpler it is compared to existing algorithms. Sometimes simpler

algorithms are also more efficient than more complicatedalternatives.

Unfortunately, it
is not always true, in which case a judicious
compromise needs to be made.
✓
Generality: Generality of the problem the algorithm solves and the set of inputs it
accepts.

Dept of CSE-CY Page 5

ADA module-1
✓
If not satisfied with these three properties it is necessary to redesign the algorithm.
• Code the algorithm
✓
Writing program by using programming language.
✓
Selection of programming language should support the features mentioned in
the design phase.
✓
Program testing: If the inputs to algorithms belong to the specified sets then
require no verification. But while implementing algorithms as programs to be
used in actual applications, it is required to provide such verifications.
✓ Documentation of the algorithm is also important.

1.2 Algorithm Specification

Algorithm can be described in three ways.

1. Natural language like English: When this way is choosed care should be taken, we
should ensure that each & every statement is definite.
2. Graphic representation called flowchart: This method will work well when the
algorithm is small& simple.
3. Pseudo-code Method: In this method, we should typically describe algorithms as
program, which resembles programming language constructs
Pseudo-Code Conventions:
1. Comments begin with // and continue until the end of line.
2. Bocks are indicated with matching braces {and}.
An identifier begins with a letter. The data types of variables are not explicitly
[Link].
4. Compound data types can be formed with records. Here is an example,
data type – n data – n; node * link;
Node. Record { data type – 1 data-1; . . . }
Here link is a pointer to the record type node. Individual data items of a record can be
accessed with → and period.
5. Assignment of values to variables is done using the assignment statement.
<Variable>:= <expression>;
6. There are two Boolean values TRUE and FALSE.
✓
Logical Operators AND, OR, NOT

Dept of CSE-CY Page 6

DAA module-1

✓
Relational Operators <, <=,>,>=, =, !=
7. The following looping statements are employed. For, while and repeat-until

While Loop:
While < condition > do
{ <statement-1> . . . <statement-n> }
For Loop:
For variable: = value-1 to value-2 step step do
{ <statement-1> . . . <statement-n> }
repeat-until:
repeat <statement-1> . . . <statement-n> until<condition>
8. A conditional statement has the following forms.
✓
If <condition> then <statement>
✓
If <condition> then <statement-1> Else <statement-1>
✓
Case
statement:
Case
{ : <condition-1> : <statement-1>

...
: <condition-n> : <statement-n>
: else : <statement-n+1>
}
9. Input and output are done using the instructions read & write.
10. There is only one type of procedure:
✓
Algorithm, the heading takes the form, Algorithm Name (Parameter lists)
✓
As an example, the following algorithm fields & returns the maximum of „n‟ given numbers:

Algorithm Max(A,n)
/ A is an array of size n
{
Result := A[1];
Dept of CSD Page 7
DAA module-1
for i:= 2 to n
do
if A[i] > Result then
Result :=A[I];
return Result;
}
In this algorithm (named Max), A & n are procedure parameters. Result & i are Local
variables.
1.3 Analysis Framework

There are two kinds of efficiency:

♦ Time efficiency - indicates how fast an algorithm in question runs.
♦ Space efficiency - deals with the extra space the algorithm requires.
✓
Measuring An Input Size
♦ An algorithm's efficiency is investigated as a function of some parameter
‗n‘ indicating the algorithm's input size.
♦ In most cases, selecting such a parameter is quite straightforward.
♦ For example, it will be the size of the list for problems of sorting, searching, finding
the list's smallest element, and most other problems dealing with lists.
♦ For the problem of evaluating a polynomial p(x) of degree n, it will be the polynomial's
degree
or the number of its coefficients, which is larger by one than its degree.
♦ There are situations, of course, where the choice of a parameter indicating an input
size does matter.
• Example - computing the product of two n-by-n [Link] are two
natural measures of size for this problem.
• The matrix order n.
• The total number of elements N in the matrices being multiplied.
♦ Since there is a simple formula relating these two measures, we can easily switch
from one to the other, but the answer about an algorithm's efficiency will be
qualitatively different depending on which of the two measures we use.
♦ 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-

Dept of CSD Page 8

DAA module-1
checking algorithm? If the algorithm examines individual characters of its input, then
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 size of inputs for algorithms
involving properties of numbers (e.g., checking whether a given integer n is prime).
✓
Units For Measuring Run Time

♦ We can simply use some standard unit of time measurement-a second, a millisecond,
and so on-to measure the running time of a program implementing the algorithm.
♦ There are obvious drawbacks to such an approach. They are
♦ Dependence on the speed of a particular computer
♦ Dependence on the quality of a program implementing the algorithm
♦ The compiler used in generating the machine code
♦ The difficulty of clocking the actual running time of the program.
♦ Since we are in need to measure algorithm efficiency, we should 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 difficult and unnecessary.
♦ The main objective 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.
For e.g., The basic operation is usually the most time-consuming operation in the
algorithm‘s innermost loop

♦ Consider the following example:

Let cop be the execution time of an algorithm‘s basic operation on a particular
computer, and let C(n) be the number of times this operation needs to be executed for
this algorithm. Then we can estimate the running time T (n) of a program implementing
this algorithm on that computer by the formula
T (n) ≈ copC(n).
Total number of steps for basic operation execution, C (n) = n
Dept of CSD Page 9
DAA module-1
✓
Orders Of Growth

♦ A difference 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 previous section 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: look at Table
which contains values of a few functions particularly important for analysis of
algorithms.

Table: Values (some approximate) of several functions important for analys is of algorithms

✓
Worst-Case, Best-Case, Average Case Efficiencies

♦ Algorithm efficiency depends on the input size n. And for some algorithms efficiency
not only on input size but also on the specifics of particular or type of input.
♦ We have best, worst & average case efficiencies.

Worst-case efficiency: Efficiency (number of times the basic operation will be executed)
for the worst case input of size n. i.e. The algorithm runs the longest among all possible
inputs of size n.
Best-case efficiency: Efficiency (number of times the basic operation will be executed)

Dept of CSD Page

DAA module-1
for the best case input of size n. i.e. The algorithm runs the fastest among all possible
inputs of size n. Average-case efficiency: Average time taken (number of times the
basic operation will be executed) to solve all the possible instances (random) of the
input.
NOTE: It is not the average of worst and best case.
♦ Example: Sequential search. This is a straightforward algorithm that searches for a
given item (some search key K) in a list of n elements by checking successive elements
of the list until either a match with the search key is found or the list is exhausted.
♦ ♦ Here is the algorithm's pseudo code, in which, for simplicity, a list is
implemented as an array. (It also assumes that the second condition will not be
checked if the first one, which checks that the array's index does not exceed its
upper bound, fails.)

Clearly, the running time of this algorithm can be quite different for the same list
size n. Worst case efficiency
♦ The worst-case efficiency 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.
♦ In the worst case the input might be in such a way that there are no matching
elements or the first matching element happens to be the last one on the list, in this
case the algorithm makes the largest number of key comparisons among all possible
inputs of size n:
Cworst (n) = n.

Dept of CSD Page

DAA module-1
♦ The way to determine is quite straightforward
♦ To 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 Cworst (n).
♦ 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 Cworst (n) its running time on the
worst-case inputs.
Best case Efficiency
♦ The best-case efficiency 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.
♦ We can analyze the best case efficie ncy as follows.

First, 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 ascertain the value of C (n) on these most convenient inputs.
♦ Example- for sequential search, best-case inputs will be lists of size n with their first
element equal to a search key; accordingly, Cbest (n) = 1.
♦ 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. 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.
♦ Thus, 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.
Average case efficiency
♦ It yields the information about an algorithm about an algorithm‗s behaviour on a

Dept of CSD Page

DAA module-1
―typical and random input.
♦ To analyze the algorithm's average-case efficiency, we must make some assumptions
about possible inputs of size n.
♦ The investigation of the average case efficiency is considerably more difficult than
investigation of the worst case and best case efficiency.
♦ It 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.
♦ Thena probability distribution of inputs needs to be obtained or assumed so that the
expected value of the basic operation's count can then be derived. The average number
of key comparisons Cavg(n) can be computed as follows,
♦ Let us consider again sequential search. The standard
assumptions are, ♦Let p be the probability of successful search.
t
♦ In the case of a successful search, the probability of the first match occurring in the i
h
position of the list is p/n for every i, where 1<=i<=n and the number of comparisons
made by the algorithm in such a situation is obviously i.
♦ In the case of an unsuccessful search, the number of comparisons is n with the
probability of such a search being (1 - p). Therefore,

Example, if p = 1 (i.e., the search must be successful), the average number of key
comparisons made by sequential search is (n + 1) /2.
♦ If p = 0 (i.e., the search must be unsuccessful), the average number of key
comparisons will be n because the algorithm will inspect all n elements on all such
inputs.

Dept of CSD Page

DAA module-1
Recapitulation of the Analysis Framework
1 Both time and space efficiencies are measured as functions of the algorithm‘s
input size.
2 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.
3 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.
4 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.

2. PERFORMANCE ANALYSIS
2.1 Space complexity

• Total amount of computer memory required by an algorithm to complete its

execution is called as space complexity of that algorithm.

• The Space required by an algorithm is the sum of following components

✓
A fixed part that is independent of the input and output. This includes memory
space for codes, variables, constants and so on.
✓
A variable part that depends on the input, output and recursion stack. ( We call
these parameters as instance characteristics)
• Space requirement S(P) of an algorithm P,

S(P) = c + Sp

where c is a constant depends on the fixed part, Sp is the instance characteristics

Example-1: Consider following algorithm abc()
Algorithm abc(a,b,c)
{
return a+b++*c+(a+b-c)/(a+b) +4.0;
}

Dept of CSD Page

DAA module-1
Here fixed component depends on the size of a, b and c. Also instance characteristics
Sp=0

Example-2: Let us consider the algorithm to find sum of array.

For the algorithm given here the problem instances are characterized by n, the number
of elements to be summed. The space needed by a[ ] depends on n. So the space
complexity can be written as; Ssum(n) ≥ (n+3) n for a[ ], One each for n, i and

2.2 Time Complexity

• The time T(p) taken by a program P is the sum of the compile time and the run
time(execution time)
✓
The compile time does not depend on the instance characteristics. Also we may
assume that a compiled program will be run several times without recompilation .
✓ The run time is denoted by tp(instance characteristics).

• Usually, the execution time or run-time of the program is refered as its time
complexity denoted by tp (instance characteristics). This is the sum of the time
taken to execute all instructions in the program.
✓ .
For example comment has zero steps; assignment statement has one step and in
an iterative statement such as the for, while & repeat-until statements, the step

Dept of CSD Page

DAA module-1
count is counted for the control part of the statement
• We can determine the steps needed by a program to solve a particular problem
instance in two ways
✓
In the first method we introduce a new variable count to the program which is
initialized to zero. We also introduce statements to increment count by an
appropriate amount into the program. So when each time original program
executes, the count also incremented by the step count.
✓
Example-1: Consider the algorithm Sum( ). After the introduction of the count the

From the above we can estimate that invocation of Sum( ) executes total
number of 2n+3 steps.
✓
Example-2:Consider the algorithm that computes Sum of n numbers recursively

▪
When analyzing a recursive program for its step count, we often obtain

Dept of CSD Page

DAA module-1
A recursive formula for the step count, for example

These recursive formulas are referred to as recurrence relations. One way of

solving is to make repeated substitutions for each occurrence of the function
tRSum on the right-hand side until all such occurrences disappear

▪
So, the step count for RSum is 2n+2
✓
The second method to determine the step count of an algorithm is to build a
t▪able in which we list the total number of steps contributes by each statement.
First determine the number of steps per execution (s/e) of the statement and

number of times (ie., frequency) each statement is executed.

▪
By combining these two quantities, the total contribution of all statements,
the step count for the entire algorithm is obtained.
✓ Example 1: Consider the algorithm sum( ).

Table: Step table for the Sum() algorithm

Dept of CSD Page

DAA module-1

Example 2: Consider the algorithm that computes Sum of n numbers recursively

Table: Step table for the RSum() algorithm

3. ASYMPTOTIC NOTATIONS

algorithm‘s basic operation count as the principal indicator of the algorithm‘s efficiency.

Θ (big theta).

Indeed, the first two functions are linear and hence have a lower order of growth than g(n)
2 2
= n , while the last one is quadratic and hence has the same order of growth as n . On the

other hand,

Dept of CSD Page

DAA module-1

3 3
Indeed, the functions and 0.00001 are both cubic and hence have a higher order of
n n
2 4
growth than n , and so has the fourth-degree polynomial n + n + 1.
The second notation, Ω (g(n)), stands for the set of all functions with a higher or same
order of growth as g(n) (to within a constant multiple, as n goes to infinity).
For example,

Finally, Θ (g(n)) is the set of all functions that have the same order of growth as g(n).

The definition is illustrated in the following figure.

Dept of CSD Page

DAA module-1

The definition is illustrated in the following figure.

Examples: Refer class notes

❖
Useful property involving the asymptotic notations

Dept of CSD Page

DAA module-1
Using the formal definitions of the asymptotic notations, we can prove their general
properties. The following property, in particular, is useful in analyzing algorithms that
comprise two consecutively executed parts
DAA module-1

Dept of CSD Page

DAA module-1

4. MATHEMATICAL ANALYSIS OF NON-RECURSIVE ALGORITHMS

General plan for analyzing efficiency of non-recursive algorithms:

1. Decide on parameter n indicating the input size of the algorithm.

2. Identify algorithm‘s basic operation.
3. Check whether the number of times the basic operation is executed depends only on
the input size n. If it also depends on the type of input, then investigate worst, average,
and best case efficiency separately.
4. Set up summation for C(n) reflecting the number of times the algorithm‘s basic
operation is executed.
5. Simplify summation using standard formulas(Refer class notes for formulas used
for simplifying).

Example: Finding the largest element in a given array

Analysis:

Dept of CSD Page

DAA module-1
1. Input size: the number of elements = n (size of the array)
2. Two operations can be considered to be as basic operation i.e.,
a)Comparison ::A[i]>maxval.
b) Assignment :: maxval←A[i].
Here the comparison statement is considered to be the basic operation of the
algorithm.
3. No best, worst, average cases- because the number of comparisons will be same for
all arrays of size n and it is not dependent on type of input.
4. Let C(n) denotes number of comparisons: Algorithm makes one comparison on
each execution of the loop, which is repeated for each value of the loop‘s variable i
within the bound
between 1 and n – 1.

Dept of CSD Page

DAA module-1

Example: Element uniqueness problem-Checks whether the elements in the array are
distinct or not.

Analysis
Input size: number of elements = n (size of the array)
Basic operation: Comparison
Best, worst, average cases exists

Array with no equal elements

Array with last two elements are the only pair of equal elements
4. Let C (n) denotes number of comparisons in worst case: Algorithm makes one
comparison for
each repetition of the innermost loop i.e., for each value of the loop‘s variable j between
its limits i + 1 and n – 1; and this is repeated for each value of the outer loop i.e, for
each value of the loop‘s variable i between its limits 0 and n – 2.

Dept of CSD Page

DAA module-1

5. Simplify the summation using standard formulas as follows:

Example 3: Given two n × n matrices A and B, find the time efficiency of the definition-
based algorithm for computing their product C = AB. By definition, C is an n × n matrix
whose elements are computed as the scalar (dot) products of the rows of matrix A and
the columns of matrix B:

Dept of CSD Page

DAA module-1

Analysis:

1. We measure an input‘s size by matrix order n.

2. 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. Hence, we consider multiplication as the basic operation.
3. Let us set up a sum for the total number of multiplications M(n) executed by the
algorithm. (Since this count depends only on the size of the input matrices, we do not
have to investigate the worst-case, average-case, and best-case efficiencies separately.)
4. Obviously, there is just one multiplication executed on each repetition of the

Dept of CSD Page

DAA module-1
algorithm‘s
innermost loop, which is governed by the variable k ranging from the lower bound 0 to
the upper bound n − 1. Therefore, the number of multiplications made for every pair of
specific values of variables i and j is

Now, we can compute this sum by using formula (S1) and rule (R1). Starting with the
innermost sum, which is equal to n, we get

Example 4: The following algorithm finds the number of binary digits in the binary
representation of a positive decimal integer

Dept of CSD Page

DAA module-1

✓
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 log2 n.
✓
The exact formula for the number of times the comparison n>1 will be executed is
actually

the number of bits in the binary representation of n.

5. MATHEMATICAL ANALYSIS(TIME EFFICIENCY) OF RECURSIVE

ALGORITHMS
General plan for analyzing efficiency of recursive algorithms:
1. Decide on parameter n indicating input size
2. Identify algorithm‘s basic operation
3. Check whether the number of times the basic operation is executed depends only
on the input size n. If it also depends on the type of input, investigate worst, average,
and best case efficiency separately.
4. Set up recurrence relation, with an appropriate initial condition, for the number of
times the
algorithm‘s basic operation is executed.
5. Solve the recurrence.

Example 1: Factorial function

Dept of CSD Page

DAA module-1
Definition: n ! = 1 * 2 * … *(n-1) * n for n ≥ 1 and 0! = 1
Recursive definition of n!: F(n) = F(n-1) * n for n ≥ 1 and
F(0) = 1

Analysis:
Input size: given number = n
Basic operation: multiplication
No best, worst, average cases.
Let M(n) denotes number of multiplications

5. Solve the recurrence relation using backward substitution method:

M(n) = M(n-1) + 1 substitute M(n-1)= M(n-2) + 1

+2
= (M(n-2) + 1) + 1 = M(n-2) substitute M(n-2)= M(n-3) + 1
= (M(n-3) + 1) + 2 = M(n-3) + 3

The general formula for the above pattern for some ‗i‘ is as follows:
= M(n-i) + i
By taking the advantage of the initial condition given i.e.,M(0)=0, we now substitute i=n
in the patterns formula to get the ultimate result of the backward substitutions.
=M(n-n)+n

Dept of CSD Page

DAA module-1
= M(0) + n
M(n) = n

The number of multipilcations to compute the factorial of ‗n‘ is n where the time
complexity is linear.

Example 2: Tower of Hanoi Problem

In this puzzle, we have n disks of different sizes that can slide onto any of three pegs.
Initially, all the disks are on the first peg in order of size, the largest on the bottom and
the smallest on top. The goal is to move all the disks to the third peg, using the second
one as an auxiliary, if necessary. We can move only one disk at a time, and it is
forbidden to place a larger disk on top of a smaller one.

The problem has an elegant recursive solution, which is illustrated in Figure.

✓
To move n>1 disks from peg 1 to peg 3 (with peg 2 as auxiliary):
• we first move recursively n − 1 disks from peg 1 to peg 2 (with peg 3 as
auxiliary).
• Then move the largest disk i.e., nth disk directly from peg 1 to peg 3.
• And, finally, move recursively n − 1 disks from peg 2 to peg 3 (using peg 1
as auxiliary).
✓
Of course, if n = 1, we simply move the single disk directly from the source peg to
the destination peg.

Analysis:
Let us apply the general plan outlined above to the Tower of Hanoi problem.

Dept of CSD Page

DAA module-1

1. The number of disks n is the obvious choice for the input‘s size indicator.
2. Moving one disk as the algorithm‘s basic operation.
3. Clearly, the number of moves M(n) depends on n only, and we get the following
recurrence equation for it:
M(n) = M(n-1)+ 1+M(n-1) for n>1,

M(n) = 2M(n-1) + 1, M(1) = 1 and

The initial condition is:
M(1) = 1 for n=1
5. Solve the recurrence relation using backward substitution method

M(n) = 2M(n-1) + 1 sub. M(n− 1) = 2M(n− 2) + 1

2(2M(n-2) + 1) + 1 = 2^2*M(n-2) + 2^1 + 2^0 sub. M(n −2) = 2M(n −3) + 1

= 2^2*(2M(n-3) + 1) + 2^1 + 2^0

= 2^3*M(n-3) + 2^2 + 2^1 + 2^0
=…

Since the initial condition is specified for n = 1, which is achieved for i = n − 1, we get
the following formula for the solution to recurrence

Thus, we have an exponential algorithm, which will run for an unimaginably long time
even for moderate values of n .This is not due to the fact that this particular algorithm
is poor; in fact, it is not difficult to prove that this is the most efficient algorithm
possible for this problem. It is the problem‘s intrinsic difficulty that makes it so
computationally hard.

EXAMPLE 3 A recursive version of the algorithm that computes number of binary digits
inn‘sbinary representation.

Dept of CSD Page

DAA module-1

✓
Let us set up a recurrence and an initial condition for the number of additions A(n)
made by the algorithm.
✓
The number of additions made in computing , plus one more addition is made by
the algorithm to increase the returned value by 1. This leads to the recurrence
✓

✓
Since the recursive calls end when n is equal to 1 and there are no additions madethen,
the initial condition is
A(1) = 0. for n=1
✓
The presence of _n/2_ in the function‘s argument makes the method of backward
substitutions stumble on values of n that are not powers of 2.
✓
Therefore, the standard approach to solving such a recurrence is to solve it only for
k
n = 2 and then take advantage of the theorem called the smoothness rule, which
claims that under
k
very broad assumptions the order of growth observed for n =2 gives a correct
answer about the order of growth for all values of n. (Alternatively, after getting a
solution for powers of
2, we can sometimes fine-tune this solution to get a formula valid for an arbitraryn.)
✓ k
Applying the same to the recurrence, for n = 2 which takes the form

Dept of CSD Page

DAA module-1

✓ After being initialized as a collection of n one-element subsets, the collection is

subjected to a sequence of intermixed union and search operations. This problem
is called the set unionproblem.

Dept of CSD Page