Design and Analysis of Algorithms

UNIT 1: INTRODUCTION
❖ DEFINITION OF 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 i/p into the o/p.

An algorithm as defined as finite number of unambiguous instructions to solve a

particular problem.

Observe the following activities to see how an algorithm is used to produce the
desire result.
The solution to a given problem is expressed in the form of an algorithm.
The algorithm is converted into a program.
The program when it is executed, accept the input and produces the desired output.

❖ CHARACTERISTICS OF AN ALGORITHM
1) Input specified
An algorithm should have 0 or more well-defined inputs.
2) Output specified
An algorithm should have 1 or more well-defined outputs, and should match the desired
output.

KLE Society’s JT BCA College, Gadag Page 1

 Design and Analysis of Algorithms

3) Definiteness
Algorithms must specify every step and the order the steps must be taken in the process.
Definiteness means specifying the sequence of operations for turning input into output.
Algorithm should be clear and unambiguous.
4) Effectiveness
For an algorithm to be effective, all those steps that are required to get to output must be
feasible with the available resources. It should not contain any unnecessary and
redundant steps which could make an algorithm ineffective.
5) Finiteness
The algorithm must stop, eventually. Stopping may mean that you get the expected
output OR you get a response that no solution is possible. Algorithms must terminate
after a finite number of steps. An algorithm should not be infinite.
6) Independent
An algorithm should have step-by-step directions, which should be independent of any
programming code. It should be such that it could be run on any of the programming
languages.

Issues or study of Algorithm:

• How to device or design an algorithm creating and algorithm.
• How to express an algorithm definiteness.
• How to analysis an algorithm time and space complexity.
• How to validate an algorithm fitness.
• Testing the algorithm checking for error.

An algorithm must satisfy the following criteria:

Input: Each algorithm should have zero or more inputs. The range of inputs for
which algorithm works should be satisfied.
Output: The algorithm should produce correct results. At least one output has to be
produced.

KLE Society’s JT BCA College, Gadag Page 2

 Design and Analysis of Algorithms

Definiteness: Each instruction should be clear and unambiguous.

Effectiveness: The instructions should be simple and should transform the given
input to the desired output.
Finiteness: The algorithm must terminate after a finite sequence of instructions

 Fundamentals of Algorithmic problem solving:

(i) Understanding the Problem:

 This is the first step in designing of algorithm.
 Read the problem’s description carefully to understand the problem statement
completely.
 Ask questions for clarifying the doubts about the problem
 Identify the problem types and use existing algorithm to find solution.
 Input (instance) to the problem and range of the input get fixed.

KLE Society’s JT BCA College, Gadag Page 3

 Design and Analysis of Algorithms

Decision making:
(ii)
Ascertaining the Capabilities of the Computational Device:
 In random-access machine (RAM), instructions are executed one after another
(The central assumption is that one operation at a time). Accordingly,
algorithms designed to be executed on such machines are called sequential
algorithms.
 Choice of computational devices like Processor and memory is mainly based
on space and time efficiency
Choosing between Exact and Approximate Problem Solving:
 An algorithm used to solve the problem exactly and produce correct result is
called an exact algorithm.
 If the problem is so complex and not able to get exact solution, then we have
to choose an algorithm called an approximation algorithm. i.e., produces an
approximate answer. E.g., extracting square roots, solving nonlinear
equations, and evaluating definite integrals.
Algorithm Design Techniques:
 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. (used to solve different problems
such as brute force, divide and conquer, greedy method, dynamic
programming and so on).
 Implementation is only possible with the help of Algorithms and Data
Structures.

(iii) 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.

KLE Society’s JT BCA College, Gadag Page 4

 Design and Analysis of Algorithms

3. Pseudo-code Method:
In this method, we should typically describe algorithms as program, which resembles
language like Pascal & algol.
Pseudo-Code Conventions:
1) .Algorithm consists of Head and Body
Head: Algorithm Name(Parameter List)

Body: 1 or more statements enclosed in { }

->Comments begin with //

->Assignment statements

->Using Operators

->Input and Output statements using”read”,”write “ words

->Control Statements: by using if,if then else

->Use of Loops: by using for,while,do-while..

KLE Society’s JT BCA College, Gadag Page 5
 Design and Analysis of Algorithms

Example Algorithm: GCD of 2 No.s using Euclid’s Algorithm

ALGORITHM GCD(m,n)

//INPUT: m and n should be +ve integers

// GCD of m,n

Step 1: Repeat as long as M and N are different

Step 1: If M>N,subtract N from M,store result in M,

Step 2: If M<N,Subtract M from N and store the result in N

Step 2: return M or N

Repetitive subtraction (Euclid’s Algorithm)

EXAMPLE: M=10,N=6

(iv) Proving an Algorithm’s Correctness:

 Once the algorithm has been specified then its correctness must be proved.
 An algorithm must yield a required result for every legitimate input in a finite
amount of time.

(v) Analyzing an Algorithm:

 Time efficiency: indicating how fast the algorithm runs
 Space sufficiency: indicating how much extra memory it uses

KLE Society’s JT BCA College, Gadag Page 6

 Design and Analysis of Algorithms

 The efficiency of an algorithm is measured by both time efficiency and space

efficiency.
 Factors to analyze algorithm are time efficiency, space efficiency, simplicity and
generality of an algorithm.

(vi) Coding an Algorithm:

 The coding or implementation of an algorithm is done by a suitable programming
language.
 It is very important to write efficient or optimized code to reduce the burden of
compiler.

CONTROL STRUCTURES:
Control Structures are just a way to specify flow of control in programs. It basically
analyzes and chooses in which direction a program flows based on certain parameters or
conditions.

There are three basic types of control structures ,namely sequential, selection and
iteration.

1. Sequence control structure

This refers to the line-by-line execution in which statements are executed

sequentially. These statements executes in the same order in which they appear in
the script.

2. Decision control structure

Depending on whether a condition is true or false, the decision control structure may
skip the execution of entire block of statements.

KLE Society’s JT BCA College, Gadag Page 7

 Design and Analysis of Algorithms

Loop control structure

This is a control structure that allows the execution of a block of statements multiple
times until a specified condition is met.

ANALYSIS OF ALGORITHM
Analysis of algorithms is the determination of the amount of time and space resources
required to execute it.
Analysis of an algorithm can be done by measuring its Performance and Complexity
● Performance: How much time/memory/disk/etc. is used when a program is run.
This depends on the machine, compiler, etc. as well as the code we write.
● Complexity: How do the resource requirements of a program or algorithm scale,
i.e. what happens as the size of the problem being solved by the code gets larger.

KLE Society’s JT BCA College, Gadag Page 8

 Design and Analysis of Algorithms

SPACE COMPLEXITY
Space complexity is the amount of memory used by the algorithm (including the input
values to the algorithm) to execute and produce the result.

Space Complexity Depends on

● Program Space : Space required to store compiled instructions

● Data Space : Space to store constants variable etc..
● Stack Space : Sometimes an algorithm(function) may be called inside another
algorithm(function). In such a situation, the current variables are pushed onto the
system stack, where they wait for further execution and then the call to the inside
algorithm(function) is made.

But while calculating the Space Complexity of any algorithm, we usually consider only
Data Space and we neglect the Program Space and Stack Space.

EXAMPLE
{

int z=a+b+c; //4*4=16

return z; //16+4=20 BYTES

KLE Society’s JT BCA College, Gadag Page 9

 Design and Analysis of Algorithms

Space complexity=4*4+4 = 20 bytes

TIME COMPLEXITY
Time complexity of an algorithm signifies the total time required by the program to run
till its completion.

Time Complexity depends on

● Speed of computer
● Choice of the programming language
● Compiler used
● Choice of algorithm
● Size of input and output

Since time efficiency depends on the size of the i/p ‘n’,it is expressed in terms of n.

Example 1
int sum(int a, int b)
{
return a+b;
}
In the above sample code, it requires 1 unit of time to calculate a+b and 1 unit of time to
return the value. That means, totally it takes 2 units of time to complete its execution. And it
does not change based on the input values of a and b. That means for all input values, it
requires the same amount of time i.e. 2 units.

Example 2
int sum(int A[], int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
rerurn sum
}

KLE Society’s JT BCA College, Gadag Page 10

 Design and Analysis of Algorithms

sum=0 => 1 Unit of time

i=0 => 1 Unit of time

i<n => n+1 Unit of time

i++ => n Unit of time

sum=sum+A[i] => 2n Unit of time

return sum => 1 Unit of time

therefore the time complexity can be written as 1+1+n+1+n+2n+1=4n+4 = O(n).

Framework for Analysis

We use a hypothetical model with following assumptions
• Total time taken by the algorithm is given as a function on its input size
• Logical units are identified as one step
• Every step require ONE unit of time
• Total time taken = Total Num. of steps executed

Input’s size: Time required by an algorithm is proportional to size of the problem

instance. For e.g., more time is required to sort 20 elements than what is required to sort
10 elements.

Units for Measuring Running Time: Count the number of times an algorithm’s basic
operation is executed. (Basic operation: The most important operation of the
algorithm, the operation contributing the most to the total running time.) For e.g., The
basic operation is usually the most time-consuming operation in the algorithm’s
innermost loop.

BASIC OPERATION
● An operation which contributes towards the running time of the algorithm. OR A
statement that executes max. No. of times in a function.
● No. of times Basic operation execution depends on size of i/p.
● Time efficiency is analyzed by determining the no. of times basic operation is
executed. So
KLE Society’s JT BCA College, Gadag Page 11
 Design and Analysis of Algorithms

❖ ORDER OF GROWTH
Some algorithms execute faster for smaller values of n. But, as the value of n
increases, they tend to be very slow. So, the behavior of some algorithm changes with
increase in the value of n. This change in behavior of algorithm and algorithm’s
efficiency can be analyzed by considering the highest order of n. the order of growth is
normally determined for larger values of n for the following reasons.
 Behavior of algorithm changes with increase in values of n(size of i/p)

 The order of growth is normally determined for large value of n, because

 The algorithm behavior changes as ‘n’ increases

 In real time applications normally we encounter large value of ‘n’

If N=1, 2 pow N=2 pow 1=2

If N=2,2 pow N= 2 pow 2=4

2 pow 4=16, 2 pow 8=256…..i.e it shows exponential growth for small variation
in ‘N’.So an algorithm with linear growth is preferred over an algorithm with
exponential growth.

KLE Society’s JT BCA College, Gadag Page 12

 Design and Analysis of Algorithms

BASIC EFFICIENCY CLASSES ARE

● 1 or constant: Next instructions of most programs are executed once or at most
only a few times. If all the instructions of a program have this property, we say
that its running time is a constant.
● Log N: When the running time of a program is logarithmic, the program gets
slightly slower as n grows. This running time commonly occurs in programs that
solve a big problem by transforming it into a smaller problem, cutting the size by
some constant fraction., Example : Binary Search
● N : When the running time of a program is linear, it is generally the case that a
small amount of processing is done on each input element. When N is 1000, the
running time is 1000 units. Example : Linear Search
● N log N : This running time arises for algorithms that solve a problem by
breaking it up into smaller sub-problems, solving then independently, and then
combining the solutions. When n doubles, the running time more than doubles.
Example : Merge Sort, Quick Sort and Heap Sort
● N2 : When the running time of an algorithm is quadratic, it is practical for use
only on relatively small problems. Quadratic running times typically arise in
algorithms that process all pairs of data items with two nested loops. Whenever n
doubles, the running time increases four fold. Example : Bubble Sort, Selection
Sort and Addition and Subtraction of Two Matrices
● N3 : The running time of a program is cubic. Similarly, an algorithm that process
triples of data items with three nested loops. Whenever n doubles, the running
time increases eight fold. Example : Matrix Multiplication
● 2N : The running time of an algorithm is exponential. Few algorithms with
exponential running time are likely to be appropriate for practical use, such
algorithms arise naturally as “brute–force” solutions to problems. Example :
Tower of Hanoi

● N! : The running time of an algorithm is factorial. The algorithm that generate all
permutations of set will have this running time.

KLE Society’s JT BCA College, Gadag Page 13

 Design and Analysis of Algorithms

1 or constant<log n<n<n log n<n2<n3<2n<n!

Example: Suppose you have analyzed two algorithms and expressed their run times in
terms of the size of the input: Algorithm A takes 100 n + 1 steps to solve a problem with
size n; Algorithm B takes n2 + n + 1 steps.

The following table shows the run time of these algorithms for different problem sizes:

Input Size Run time of Algorithm A Run time of Algorithm B

10 1001 111

100 10001 10101

1000 100001 1001001

10000 1000001 >1010

KLE Society’s JT BCA College, Gadag Page 14

 Design and Analysis of Algorithms

 TYPES OF EFFICIENCIES:

1. Best case Efficiency: Define the input for which algorithm takes less time or
minimum time. In the best case calculate the lower bound of an algorithm. Example: In
the linear search when search data is present at the first location of large data then the
best case occurs. Efficiency (number of times the basic operation will be executed) for
the best case input of size n. i.e. The algorithm runs the fastest among all possible
inputs of size n.

2. Average case efficiency : In the average case take all random inputs and calculate
the computation time for all inputs. And then we divide it by the total number of inputs.
Average time taken (number of times the basic operation will be executed) to solve all
the possible instances (random) of the input. NOTE: NOT the average of worst and
best case.

3. Worst Case Efficiency: Define the input for which algorithm takes a long time or
maximum time. In the worst calculate the upper bound of an algorithm. Example: In the
linear search when search data is not present at all then the worst case occurs. 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.

KLE Society’s JT BCA College, Gadag Page 15

 Design and Analysis of Algorithms

ASYMPTOTIC NOTATIONS

Asymptotic notations are the mathematical notations used to describe the running time
of an algorithm when the input tends towards a particular value or a limiting value.

There are mainly three asymptotic notations:

 Big-O notation(O-notation)-->UPPER BOUND OF FUNCTION

● Omega notation(Ω Notation) --->LOWER BOUND OF FUNCTION
● Theta notation (Θ Notation) --->AVERAGE BOUND OF A FUNCTION

➔ Big-O Notation (O-notation)

This notation provides an upper bound on the growth rate of an algorithm’s running
time or space usage. It represents the worst-case scenario, i.e., the maximum amount of
time or space an algorithm may need to solve a problem. For example, if an algorithm’s
running time is O(n), then it means that the running time of the algorithm increases
linearly with the input size n or less.

f(n)=O(g(n)) iff ∃ +ve constant C and no

Such that f(n)≤ c*g(n) ∀ n≥no

The above expression can be described as a function f(n) belongs to the set O(g(n)) if
there exists a positive constant c and no such that, f(n)≤ c*g(n) for all n≥no For any
value of n, the running time of an algorithm does not cross the time provided by
O(g(n)).

KLE Society’s JT BCA College, Gadag Page 16

 Design and Analysis of Algorithms

Example

Consider the following f(n) and g(n) two non negative functions…

f(n)=3n+2 g(n)=n If we want to represent f(n) as O(g(n)) then it must satisfy f(n)
<= C*g(n) for all values of C > 0 and n0>=1

f(n)<=C*g(n) ⇒3n+2<=C*n

3n+2<=C*n (let C=4)

3n+2<=4*n (let n=n0=1)

KLE Society’s JT BCA College, Gadag Page 17

 Design and Analysis of Algorithms

3*1+2<=4*1 5<=4 (Condition not satisfied) 3n+2<=4*n (let n=n0=2)

3*2+2<=4*2

8<=8 (Condition satisfied)

Then f(n)<=C*g(n)¥n>=2 Above condition is always TRUE for all values of C =

4 and n >= 2.

➔ OMEGA ( Ω ) NOTATION
This notation provides a lower bound on the growth rate of an algorithm’s running time
or space usage. It represents the best-case scenario, i.e., the minimum amount of time or
space an algorithm may need to solve a problem. For example, if an algorithm’s running
time is Ω(n), then it means that the running time of the algorithm increases linearly with
the input size n or more.

f(n)=Ω(g(n)) : there exist positive constants c and n0

such that f(n) ≥ c*g(n) for all n≥ n0

KLE Society’s JT BCA College, Gadag Page 18

 Design and Analysis of Algorithms

Example

Consider the following f(n) and g(n) two non negative functions…
f(n)=3n+2 g(n)=n If we want to represent f(n) as Ω(g(n)) then it must satisfy f(n) >= C
g(n) for all values of C>0 and n0>=1
f(n)>=C*g(n) ⇒3n+2>=C*n
3n+2>=C*n (let C=1)
3n+2>=1*n (let n=n0=1)
3*1+2>=1*1
5>=1(Condition satisfied)
Then f(n)>=C*g(n)¥n>=1 Above condition is always TRUE for all values of C = 1 and
n >= 1.

KLE Society’s JT BCA College, Gadag Page 19

 Design and Analysis of Algorithms

Theta Notation (Θ-notation)

This notation provides both an upper and lower bound on the growth rate of an
algorithm’s running time or space usage. It represents the average-case scenario, i.e., the
amount of time or space an algorithm typically needs to solve a problem. For example,
if an algorithm’s running time is Θ(n), then it means that the running time of the
algorithm increases linearly with the input size n.
Θ(g(n)) = {f(n): there exist positive constants

c1, c2 and n0 such that

c1*g(n) <= f(n) <= c2*g(n)

for all n >= n0}

Example

Consider the following f)n) and g(n) two non negative functions… f(n)=3n+2 g(n)=n If
we want to represent f(n) as Θ(g(n)) then it must satisfy C1*g(n) <= f(n) <= C2*g(n) for
all values of C1 >0,C2 >0 and n0>=1

KLE Society’s JT BCA College, Gadag Page 20

 Design and Analysis of Algorithms

C1*g(n)<=f(n)<=C2*g(n) ⇒C1*n<=3n+2<=C2*n
C1*n<=3n+2<=C2*n (let C1=1 and C2=4)
1*n<=3n+2<=4*n (let n=n0=1)
1*1<=3*1+2<=4*1
1<=5<=4 (Condition not satisfied)
1*n<=3n+2<=4*n (let n=n0=2)
1*2<=3*2+2<=4*2
2<=8<=8 (Condition satisfied)
Then C1 g(n)<=f(n)<=C2 g(n) ¥n>=2 Above condition is always TRUE for all values of
C1 = 1, C2 = 4 and n >= 2.

Types of Algorithms: There are several types of algorithms available.

Some important algorithms are:

1. Brute Force Algorithm: This is the most basic and simplest type of algorithm. A
Brute Force Algorithm is the straightforward approach to a problem i.e., the first
approach that comes to our mind on seeing the problem. More technically it is just like
iterating every possibility available to solve that problem.
Example: If there is a lock of 4-digit PIN. The digits to be chosen from 0-9 then the
brute force will be trying all possible combinations one by one like 0001, 0002, 0003,
0004, and so on until we get the right PIN. In the worst case, it will take 10,000 tries to
find the right combination.

2.Recursive Algorithm: This type of algorithm is based on recursion. In recursion, a

problem is solved by breaking it into sub problems of the same type and calling own
self again and again until the problem is solved with the help of a base condition. Some
common problem that is solved using recursive algorithms are Factorial of a Number,
Fibonacci Series, Tower of Hanoi, DFS for Graph, etc.

3.Divide and Conquer Algorithm: In Divide and Conquer algorithms, the idea is to
solve the problem in two sections, the first section divides the problem into sub
problems of the same type. The second section is to solve the smaller problem
independently and then add the combined result to produce the final answer to the
problem. Some common problem that is solved using Divide and Conquers Algorithms
are Binary Search, Merge Sort, Quick Sort, Strassen’s Matrix Multiplication, etc.

4.Dynamic Programming Algorithms: This type of algorithm is also known as the

memorization technique because in this the idea is to store the previously calculated
result to avoid calculating it again and again. In Dynamic Programming, divide the

KLE Society’s JT BCA College, Gadag Page 21

 Design and Analysis of Algorithms

complex problem into smaller overlapping sub problems and store the result for future
use. The following problems can be solved using the Dynamic Programming algorithm
Knapsack Problem, Weighted Job Scheduling, Floyd Warshall Algorithm, etc.

5.Greedy Algorithm: In the Greedy Algorithm, the solution is built part by part. The
decision to choose the next part is done on the basis that it gives an immediate benefit. It
never considers the choices that had been taken previously. Some common problems
that can be solved through the Greedy Algorithm are Dijkstra Shortest Path Algorithm,
Prim’s Algorithm, Kruskal’s Algorithm etc.

6.Backtracking Algorithm: In Backtracking Algorithm, the problem is solved in an

incremental way i.e. it is an algorithmic technique for solving problems recursively by
trying to build a solution incrementally, one piece at a time, removing those solutions
that fail to satisfy the constraints of the problem at any point of time. Some common
problems that can be solved through the Backtracking Algorithm are the Hamiltonian
Cycle, Sum of Subset, N Queen Problem etc.

7. Randomized Algorithm: In the randomized algorithm, we use a random number.it

helps to decide the expected outcome. The decision to choose the random number so it
gives the immediate benefit Some common problems that can be solved through the
Randomized Algorithm are Quicksort: In Quicksort we use the random number for
selecting the pivot.

8. Sorting Algorithm: The sorting algorithm is used to sort data in maybe ascending or
descending order. It’s also used for arranging data in an efficient and useful manner.
Some common problems that can be solved through the sorting Algorithm are Bubble
sort, insertion sort, selection sort etc are examples of the Sorting algorithm.

9. Searching Algorithm: The searching algorithm is the algorithm that is used for
searching the specific key in particular sorted or unsorted data. Some common problems
that can be solved through the Searching Algorithm are Binary search or linear search is
one example of a Searching algorithm.

10. Hashing Algorithm: Hashing algorithms work the same as the Searching algorithm
but they contain an index with a key ID i.e. a key-value pair. In hashing, we assign a
key to specific data. Some common problems can be solved through the Hashing
Algorithm in password

KLE Society’s JT BCA College, Gadag Page 22

 Design and Analysis of Algorithms

Basic Efficiency classes

The time efficiencies of a large number of algorithms fall into only a few classes.

Mathematical analysis (Time Efficiency) of Non-recursive Algorithms

General plan for analyzing efficiency of non-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 is dependent on some other condition, then it is necessary to
obtain the worst case, best case and average case efficiency separately.
4. Obtain the total number of times the algorithm’s a basic operation is executed.
5. Simplify summation using standard formulas and obtain the order of growth.

KLE Society’s JT BCA College, Gadag Page 23

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 24

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 25

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 26

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 27

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 28

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 29

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 30

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 31

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 32

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 33

 Design and Analysis of Algorithms

Write an algorithm to find the Maximum and Minimum numbers in array and time
efficiency of the algorithm.

KLE Society’s JT BCA College, Gadag Page 34

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 35

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 36

 Design and Analysis of Algorithms

Mathematical analysis (Time Efficiency) of recursive Algorithms

General plan for analyzing efficiency of recursive algorithms:

1. Identify the parameters based on the size of the input
2. Identify the basic operation in the algorithm
3. Obtain the number of times the basic operation is executed on different inputs of the
same size. If it varies then it is necessary to obtain the worst case, best case and average
case separately
4. Obtain a recurrence relation, with an appropriate initial condition
5. Solve the recurrence relation and obtain the order of growth and express using
asymptotic notations

KLE Society’s JT BCA College, Gadag Page 37

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 38

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 39

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 40

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 41

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 42

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 43

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 44

 Design and Analysis of Algorithms

KLE Society’s JT BCA College, Gadag Page 45