Department of Information Technology

Central University of Kashmir

Tullmulla, Ganderbal, J&K-191131
www.cukashmir.ac.in

BTCS 603
Design & Analysis of Algorithm

UNIT I

Sub Topic(s): Introduction To Algorithm, Algorithm

Classification, Analyzing algorithms,
Space and Time Complexity, Asymptotic
Notations, The divide-and-conquer
approach, Recurrence Relation for DAC
algorithm and Recurrence Relations.

Course Title Design & Analysis of Algorithm

Course Code: BTCS 603
Unit: I
Department: Department of IT
Year: 2020

Compiled by: Amjad Husain

Email: amjed.husain@gmail.com
Contact: <optional>
Designation: Assistant Professor
Department: Department of IT

Copyright © 2020 by Central University of Kashmir . All rights reserved.

 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Index
Section 1: Introduction
1.1. Characteristics of an Algorithm
1.2. Algorithm Design
1.3. How algorithm is a technology
1.4. Algorithm Classification
1.4.1. Classification by implementation
1.4.1.1. Recursion or iteration
1.4.1.2. Logical
1.4.1.3. Serial or parallel or distributed
1.4.1.4. Deterministic or non-deterministic
1.4.1.5. Exact or approximate
1.4.2. Classification by Design Paradigm
1.4.2.1. Divide and conquer
1.4.2.2. Dynamic programming
1.4.2.3. The greedy method
1.4.2.4. Linear programming
1.4.2.5. Reduction
1.4.2.6. Search and enumeration
1.4.2.7. The probabilistic and heuristic paradigm
1.5. Recursive Algorithms
1.6. The Need for Analysis
1.7. Algorithmic efficiency
Section 2: Analyzing algorithms
2.1. Runtime Analysis of Algorithms
2.2. Random-access machine (RAM) model
2.3. How do we analyze an algorithm’s running time
2.4. Space and Time Complexity
2.4.1. Space Complexity
2.4.2. Time Complexity
2.5. Asymptotic Notations
2.5.1. Big ‘Oh’ Notation (O)
2.5.2. Omega Notation (Ω)
2.5.3. Theta Notation (Θ)
2.5.4. Little ‘Oh’ Notation (o)
2.5.5. Little Omega (ω)
Section 3: The divide-and-conquer approach
3.1. Divide And Conquer algorithm
3.2. Recurrence Relation for DAC algorithm
3.2.1. Binary Search
3.2.2. Maximum and Minimum
3.2.3. Merge Sort
3.2.4. Quick Sort
Section 4: Recurrence Methods
4.1. Substitution Method
4.2. Recursion tree Method
4.3. Master Method

Page 2
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

1. Introduction
An algorithm is a set of steps of operations to solve a problem performing calculation,
data processing, and automated reasoning tasks. An algorithm is an efficient method
that can be expressed within finite amount of time and space.
An algorithm is the best way to represent the solution of a particular problem in a very
simple and efficient way. If we have an algorithm for a specific problem, then we can
implement it in any programming language, meaning that the algorithm is
independent from any programming languages.
The word algorithm comes from the name of a Persian author, Abu Ja'far
Mohammed ibn Musa al Khowarizmi (c. 825 A.O.) who wrote a textbook on
mathematics. an algorithm is any well-defined computational procedure that takes
some value, or set of values, as input and produces some value, or set of values, as
output. An algorithm is thus a sequence of computational steps that transform the input
into the output.
We can also view an algorithm as a tool for solving a well-specified computational
problem. The statement of the problem specifies in general terms the desired
input/output relationship. The algorithm describes a specific computational procedure
for achieving that input/output relationship.

1.1. Characteristics of an Algorithm

• Clear and Unambiguous: Algorithm should be clear and unambiguous. Each of
its steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-
defined inputs.
• Well-Defined Outputs: The algorithm must clearly define what output will be
yielded and it should be well-defined as well.
• Finite-ness: The algorithm must be finite, i.e. it should not end up in an infinite
loops or similar.
• Feasible: The algorithm must be simple, generic and practical, such that it can be
executed upon will the available resources. It must not contain some future
technology, or anything.
• Language Independent: The Algorithm designed must be language-
independent, i.e. it must be just plain instructions that can be implemented in
any language, and yet the output will be same, as expected.

1.2. Algorithm Design

The important aspects of algorithm design include creating an efficient algorithm to
solve a problem in an efficient way using minimum time and space.
To solve a problem, different approaches can be followed. Some of them can be efficient
with respect to time consumption, whereas other approaches may be memory efficient.
However, one has to keep in mind that both time consumption and memory usage
cannot be optimized simultaneously. If we require an algorithm to run in lesser time, we
have to invest in more memory and if we require an algorithm to run with lesser
memory, we need to have more time.
Inorder to write an algorithm, following things are needed as a pre-requisite:
• The problem that is to be solved by this algorithm.
• The constraints of the problem that must be considered while solving the
problem.
• The input to be taken to solve the problem.

Page 3
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

• The output to be expected when the problem the is solved.

The solution to this problem, in the given constraints.

Example
Step 1: Fulfilling the pre-requisites: As discussed above, in order to write an
algorithm, its pre-requisites must be fulfilled.
• The problem that is to be solved by this algorithm: Add 3 numbers and print
their sum.
• The constraints of the problem that must be considered while solving the
problem: The numbers must contain only digits and no other characters.
• The input to be taken to solve the problem: The three numbers to be added.
• The output to be expected when the problem the is solved: The sum of the
three numbers taken as the input.
• The solution to this problem, in the given constraints: The solution consists
of adding the 3 numbers. It can be done with the help of ‘+’ operator, or bit-wise,
or any other method.

Step 2: Designing the algorithm: Now let’s design the algorithm with the help of above
pre-requisites:
Algorithm to add 3 numbers and print their sum:
– START
– Declare 3 integer variables num1, num2 and num3.
– Take the three numbers, to be added, as inputs in variables num1, num2,
and num3 respectively.
– Declare an integer variable sum to store the resultant sum of the 3
numbers.
– Add the 3 numbers and store the result in the variable sum.
– Print the value of variable sum
– END
Step 3: Testing the algorithm by implementing it: Inorder to test the algorithm,
implement it in C language, then test it for some inputs.

Why Analyze an Algorithm?

• The most straightforward reason for analyzing an algorithm is to discover its
characteristics in order to evaluate its suitability for various applications or
compare it with other algorithms for the same application.
• The analysis of an algorithm can help us understand it better, and can suggest
informed improvements.
• Algorithms tend to become shorter, simpler, and more elegant during the
analysis process.

1.3. How algorithm is a technology ?

Algorithms are just like a technology. We all use latest and greatest processors but we
need to run implementations of good algorithms on that computer in order to properly
take benefits of our money that we spent to have the latest processor. Let’s make this
example more concrete by pitting a faster computer(computer A) running a sorting
algorithm whose running time on n values grows like n2 against a slower computer
(computer B) running asorting algorithm whose running time grows like n lg n. They
eachmust sort an array of 10 million numbers. Suppose that computer A executes 10
billion instructions per second (faster than any single sequential computer at the time
Page 4
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

of this writing) and computer B executes only 10 million instructions per second, so that
computer A is1000 times faster than computer B in raw computing power. To make the
difference even more dramatic, suppose that the world’s craftiest programmer codes
in machine language for computer A, and the resulting code requires 2n2 instructions to
sort n numbers. Suppose further that just an average programmer writes for computer
B, using a highlevel language with an inefficient compiler, with the resulting code taking
50n lg n instructions.

computer A is1000 times faster than computer B in raw computing power

• Computer A (Faster) Computer B(Slower)
• Running time grows like n .2 Grows in nlogn.
• 10 billion instructions per sec. 10 million instruction per sec
• 2n2 instruction. 50 nlogn instruction.

• Time taken=

• It is more than 5.5hrs it is under 20 mins.

So choosing a good algorithm (algorithm with slower rate of growth) as used by
computer B affects a lot.

1.4. Algorithm Classification

There are various ways to classify algorithms. They are as follows

1.4.1. Classification by implementation

1.4.1.1. Recursion or iteration: A recursive algorithm is one that invokes (makes
reference to) itself repeatedly until a certain condition
matches, which is a method common to functional programming. Iterative algorithms
use repetitive constructs like loops and sometimes additional data structures like stacks
to solve the given problems. Some problems are naturally suited for one
implementation or the other. For example, towers of hanoi is well understood in
recursive implementation. Every recursive version has an equivalent (but possibly more
or less complex) iterative version, and vice versa.
1.4.1.2. Logical: An algorithm may be viewed as controlled logical deduction. This
notion may be expressed as: Algorithm = logic + control.
The logic component expresses the axioms that may be used in the computation and the
control component determines the way in which deduction is applied to the axioms.
This is the basis for the logic programming paradigm. In pure logic programming
languages the control component is fixed and algorithms are specified by supplying only
the logic component. The appeal of this approach is the elegant semantics: a change in
the axioms has a well defined change in the algorithm.
1.4.1.3. Serial or parallel or distributed: Algorithms are usually discussed with
the assumption that computers execute one instruction of an algorithm at a time. Those
computers are sometimes called serial computers. An algorithm designed for such an
environment is called a serial algorithm, as opposed to parallel algorithms or
distributed algorithms. Parallel algorithms take advantage of computer architectures
where several processors can work on a problem at the same time, whereas distributed
algorithms utilise multiple machines connected with a network. Parallel or distributed
Page 5
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

algorithms divide the problem into more symmetrical or asymmetrical subproblems

and collect the results back together. The resource consumption in such algorithms is
not only processor cycles on each processor but also the communication overhead
between the processors. Sorting algorithms can be parallelized efficiently, but their
communication overhead is expensive. Iterative algorithms are generally parallelizable.
Some problems have no parallel algorithms, and are called inherently serial problems.
1.4.1.4. Deterministic or non-deterministic: Deterministic algorithms solve the
problem with exact decision at every step of the algorithm whereas non-deterministic
algorithm solves problems via guessing although typical guesses are made more
accurate through the use of heuristics.
1.4.1.5. Exact or approximate: While many algorithms reach an exact solution,
approximation algorithms seek an approximation that is close to the true solution.
Approximation may use either a deterministic or a random strategy. Such algorithms
have practical value for many hard problems.

1.4.2. Classification by Design Paradigm

1.4.2.1. Divide and conquer: A divide and conquer algorithm repeatedly reduces
an instance of a problem to one or more smaller instances of the same problem (usually
recursively), until the instances are small enough to solve easily. One such example of
divide and conquer is merge sorting. Sorting can be done on each segment of data after
dividing data into segments and sorting of entire data can be obtained in conquer phase
by merging them. A simpler variant of divide and conquer is called decrease and
conquer algorithm, that solves an identical sub problem and uses the solution of this
sub problem to solve the bigger problem. Divide and conquer divides the problem into
multiple sub problems and so conquer stage will be more complex than decrease and
conquer algorithms. An example of decrease and conquer algorithm is binary search
algorithm.
1.4.2.2. Dynamic programming: When a problem shows optimal substructure,
meaning the optimal solution to a problem can be constructed from optimal solutions to
sub problems, and overlapping sub problems, meaning the same sub problems are used
to solve many different problem instances, a quicker approach called dynamic
programming avoids recomputing solutions that have already been computed. For
example, the shortest path to a goal from a vertex in a weighted graph can be found by
using the shortest path to the goal from all adjacent vertices. Dynamic programming
and memoization go together. The main difference between dynamic programming and
divide and conquer is that sub problems are more or less independent in divide and
conquer, whereas sub problems overlap in dynamic programming. The difference
between dynamic programming and straightforward recursion is in caching or
memoization of recursive calls. When sub problems are independent and there is no
repetition, memoization does not help; hence dynamic programming is not a solution
for all complex problems. By using memoization or maintaining a table of sub problems
already solved, dynamic programming reduces the exponential nature of many
problems to polynomial complexity.
1.4.2.3. The greedy method: A greedy algorithm is similar to a dynamic
programming algorithm, but the difference is that solutions to the sub problems do not
have to be known at each stage; instead a "greedy" choice can be made of what looks
best for the moment. The greedy method extends the solution with the best possible
decision (not all feasible decisions) at an algorithmic stage based on the current local
optimum and the best decision (not all possible decisions) made in previous stage. It is
not exhaustive, and does not give accurate answer to many problems. But when it
Page 6
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

works, it will be the fastest method. The most popular greedy algorithm is finding the
minimal spanning tree as given by Kruskal.
1.4.2.4. Linear programming: When solving a problem using linear
programming, specific inequalities involving the inputs are found and then an attempt is
made to maximize (or minimize) some linear function of the inputs. Many problems
(such as the maximum flow for directed graphs) can be stated in a linear programming
way, and then be solved by a 'generic' algorithm such as the simplex algorithm.
1.4.2.5. Reduction: This technique involves solving a difficult problem by
transforming it into a better known problem for which we have (hopefully)
asymptotically optimal algorithms. The goal is to find a reducing algorithm whose
complexity is not dominated by the resulting reduced algorithm's. For example, one
selection algorithm for finding the median in an unsorted list involves first sorting the
list (the expensive portion) and then pulling out the middle element in the sorted list
(the cheap portion). This technique is also known as transform and conquer.
1.4.2.6. Search and enumeration: Many problems (such as playing chess) can be
modeled as problems on graphs. A graph exploration algorithm specifies rules for
moving around a graph and is useful for such problems. This category also includes
search algorithms, branch and bound enumeration and backtracking.
1.4.2.7. The probabilistic and heuristic paradigm: Algorithms belonging to this
class fit the definition of an algorithm more loosely.
Probabilistic algorithms are those that make some choices randomly (or pseudo-
randomly); for some problems, it can in fact be proven that the fastest solutions must
involve some randomness.
Genetic algorithms attempt to find solutions to problems by mimicking biological
evolutionary processes, with a cycle of random mutations yielding successive
generations of "solutions". Thus, they emulate reproduction and "survival of the fittest".
In genetic programming, this approach is extended to algorithms, by regarding the
algorithm itself as a "solution" to a problem.
Heuristic algorithms, whose general purpose is not to find an optimal solution, but an
approximate solution where the time or resources are limited. They are not practical to
find perfect solutions. An example of this would be local search, or simulated annealing.

1.5. Recursive Algorithms

A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input
values, and which obtains the result for the current input by applying simple operations
to the returned value for the smaller (or simpler) input. More generally if a problem can
be solved utilizing solutions to smaller versions of the same problem, and the smaller
versions reduce to easily solvable cases, then one can use a recursive algorithm to solve
that problem. For example, the elements of a recursively defined set, or the value of a
recursively defined function can be obtained by a recursive algorithm.
Recursive computer programs require more memory and computation compared with
iterative algorithms, but they are simpler and for many cases a natural way of thinking
about the problem.

For example consider factorial of a number, n

n! = n*(n-1)*(n-2)*...*2*1, and that 0! = 1.

In other words,

Page 7
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Function to calculate the factorial can be written as

int factorial(int n)
{
if (n == 0)
return 1;
else
return (n * factorial(n-1));
}

factorial(0)=> 1

factorial(3)
3 * factorial(2)
3 * 2 * factorial(1)
3 * 2 * 1 * factorial(0)
3*2*1*1
=> 6

This corresponds very closely to what actually happens on the execution stack in the
computer's memory.

1.6. The Need for Analysis

In this chapter, we will discuss the need for analysis of algorithms and how to choose a
better algorithm for a particular problem as one computational problem can be solved
by different algorithms.
By considering an algorithm for a specific problem, we can begin to develop pattern
recognition so that similar types of problems can be solved by the help of this algorithm.
Algorithms are often quite different from one another, though the objective of these
algorithms are the same. For example, we know that a set of numbers can be sorted
using different algorithms. Number of comparisons performed by one algorithm may
vary with others for the same input. Hence, time complexity of those algorithms may
Page 8
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

differ. At the same time, we need to calculate the memory space required by each
algorithm.
Analysis of algorithm is the process of analyzing the problem-solving capability of the
algorithm in terms of the time and size required (the size of memory for storage while
implementation). However, the main concern of analysis of algorithms is the required
time or performance. Generally, we perform the following types of analysis −
 Worst-case − The maximum number of steps taken on any instance of size a.
 Best-case − The minimum number of steps taken on any instance of size a.
 Average case − An average number of steps taken on any instance of size a.
 Amortized − A sequence of operations applied to the input of size a averaged
over time.
To solve a problem, we need to consider time as well as space complexity as the
program may run on a system where memory is limited but adequate space is available
or may be vice-versa. In this context, if we compare bubble sort and merge sort.
Bubble sort does not require additional memory, but merge sort requires additional
space. Though time complexity of bubble sort is higher compared to merge sort, we may
need to apply bubble sort if the program needs to run in an environment, where
memory is very limited.

1.7. Algorithmic efficiency

Algorithmic efficiency is a property of an algorithm which relates to the number
of computational resources used by the algorithm. An algorithm must be analyzed to
determine its resource usage, and the efficiency of an algorithm can be measured based
on usage of different resources. Algorithmic efficiency can be thought of as analogous to
engineering productivity for a repeating or continuous process.
For maximum efficiency we wish to minimize resource usage. However, different
resources such as time(the time complexity is the computational complexity that
describes the amount of time it takes to run an algorithm.) and space(the space
complexity of an algorithm or a computer program is the amount of memory space
required to solve an instance of the computational problem as a function of the size of
the input. It is the memory required by an algorithm to execute a program and produce
output.) complexity cannot be compared directly, so which of two algorithms is
considered to be more efficient often depends on which measure of efficiency is
considered most important.
For example, bubble sort and timsort are both algorithrms to sort a list of items from
smallest to largest. Bubble sort sorts the list in time proportional to the number of
elements squared (O(n2)), but only requires a small amount of extra memory which is
constant with respect to the length of the list (O(1)). Timsort sorts the list in
time linearithmic (proportional to a quantity times its logarithm) in the list's length
(O(nlogn)), but has a space requirement linear in the length of the list (O(n)). If large
lists must be sorted at high speed for a given application, timsort is a better choice;
however, if minimizing the memory footprint of the sorting is more important, bubble
sort is a better choice.

Page 9
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

2. Analyzing Algorithm
2.1. Runtime Analysis of Algorithms
In general cases, we mainly used to measure and compare the worst-case theoretical
running time complexities of algorithms for the performance analysis.
The fastest possible running time for any algorithm is O(1), commonly referred to
as Constant Running Time. In this case, the algorithm always takes the same amount of
time to execute, regardless of the input size. This is the ideal runtime for an algorithm,
but it’s rarely achievable.
In actual cases, the performance (Runtime) of an algorithm depends on n, that is the size
of the input or the number of operations is required for each input item.
The algorithms can be classified as follows from the best-to-worst performance
(Running Time Complexity):

A logarithmic algorithm – O(logn) Runtime grows logarithmically in proportion to n.

A linear algorithm – O(n) Runtime grows directly in proportion to n.
A super linear algorithm – O(nlogn) Runtime grows in proportion to n.
A polynomial algorithm – O(nc) Runtime grows quicker than previous all based on n.
A exponential algorithm – O(cn) Runtime grows even faster than polynomial
algorithm based on n.
A factorial algorithm – O(n!) Runtime grows the fastest and becomes quickly
unusable for even small values of n.

Where, n is the input size and c is a positive constant.

We want to predict the resources that the algorithm requires. Usually, running time.
In order to predict resource requirements, we need a computational model.
2.2. Random-access machine (RAM) model
• Instructions are executed one after another. No concurrent operations.
• Its too tedious to define each of the instructions and their associated time costs.
• Instead, we recognize that we will use instructions commonly found in real
computers:
• Arithmetic: add, subtract, multiply, divide, remainder, floor, ceiling). Also, shift
left/shift right (good for multiplying/dividing by 2k ).
• Data movement: load, store, copy.
• Control: conditional/unconditional branch, subroutine call and return.
Each of these instructions takes a constant amount of time.

Page 10
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

The RAM model uses integer and floating-point types.

• We don’t worry about precision, although it is crucial in certain numerical
applications.
• There is a limit on the word size: when working with inputs of size n, assume
that integers are represented by c lg n bits for some constant c ≥ 1. (lg n is a very
frequently used shorthand for log2 n.)
• c ≥ 1⇒we can hold the value of n ⇒we can index the individual elements.
• c is a constant ⇒the word size cannot grow arbitrarily.

2.3. How do we analyze an algorithm’s running time?

The time taken by an algorithm depends on the input.
• Sorting 1000 numbers takes longer than sorting 3 numbers.
• A given sorting algorithm may even take differing amounts of time on two inputs
of the same size.
• For example, we will see that insertion sort takes less time to sort n elements
when they are already sorted than when they are in reverse sorted order.
Input size: Depends on the problem being studied.
• Usually, the number of items in the input. Like the size n of the array being
sorted.
• But could be something else. If multiplying two integers, could be the total
number of bits in the two integers.
• Could be described by more than one number. For example, graph algorithm
running times are usually expressed in terms of the number of vertices and the
number of edges in the input graph.
Running time: On a particular input, it is the number of primitive operations
(steps) executed.
• Want to define steps to be machine-independent.
• Figure that each line of pseudocode requires a constant amount of time.
• One line may take a different amount of time than another, but each execution
of line i takes the same amount of time ci .
• This is assuming that the line consists only of primitive operations.
o If the line is a subroutine call, then the actual call takes constant time, but
the execution of the subroutine being called might not.
o If the line specifies operations other than primitive ones, then it might
take more than constant time. Example: .sort the points by x-coordinate.

2.4. Space and Time Complexity

Two important ways to characterize the effectiveness of an algorithm are its space
complexity and time complexity.
2.4.1. Space Complexity
Space complexity of an algorithm is the amount to memory needed by the program for
its completion. Space needed by a program has the following components:

2.4.1.1. Instruction Space

Space needed to store the compiled version of program. It depends on
i. Compiler used
ii. Options specified at the time of compilation
e.g., whether optimization specified, Is there any overlay option etc.
iii. Target computer
e.g., For performing floating point arithmetic, if hardware present or not.
Page 11
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

2.4.1.2. Data Space

Space needed to store constant and variable values. It has two components:
iv. Space for constants:
e.g., value ‘3’ in program 1.1
Space for simple variables:
e.g., variables a,b,c in program 1.1

Program 1.1
int add (int a, int b, int c)
{
return (a+b+c)/3;
}

v. Space for component variables like arrays, structures, dynamically

allocated memory.

e.g., variables a in program 1.2

Program 1.2
int Radd (int a[], int n)
1 {
2 If (n>0)
3 return Radd (a, n-1) + a[n-1];
4 else
5 return 0;
6 }

2.4.1.3. Environment stack space

Environment stack is used to store information to resume execution of partially
completed functions. When a function is invoked, following data are stored in
Environment stack.
vi. Return address.
vii. Value of local and formal variables.
viii. Binding of all reference and constant reference parameters.

Space needed by the program can be divided into two parts.

i. Fixed part independent of instance characteristics. E.g., code space,
simple variables, fixed size component variables etc.
ii. Variable part. Space for component variables with space depends on
particular instance. Value of local and formal variables.
Hence we can write the space complexity as
S(P) = c + Sp (instance characteristics)

Example 1.1
Refer Program 1.1
One word for variables a,b,c. No instance characteristics. Hence S p(TC) = 0

Example 1.2
Program 1.3
Page 12
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

int Aadd (int *a, int n)

1 {
2 int s=0;
3 for (i=0; i<n; i++)
4 s+ = a[i];
5 return s;
6 }
One word for variables n and i. Space for a[] is address of a[0]. Hence it requires one
word. No instance characteristics. Hence Sp(TC) = 0

Example 1.3
Refer Program 1.2
Instance characteristics depend on values of n. Recursive stack space includes
space for formal parameters, local variables and return address. So one word each for
a[],n, return address and return variables. Hence for each pass it needs 4 words. Total
recursive stack space needed is 4(n).
Hence Sp(TC) = 4(n).

2.4.2. Time Complexity

Time complexity of an algorithm is the amount of time needed by the program for its
completion. Time taken is the sum of the compile time and the execution time. Compile
time does not depend on instantaneous characteristics. Hence we can ignore it.

Program step: A program step is syntactically or semantically meaningful segment of a

program whose execution time is independent of instantaneous characteristics. We can
calculate complexity in terms of

1. Comments:
No executables, hence step count = 0

2. Declarative Statements:
Define or characterize variables and constants like (int , long, enum, …)
Statement enabling data types (class, struct, union, template)
Determine access statements ( public, private, protected, friend )
Character functions ( void, virtual )
All the above are non executables, hence step count = 0

3. Expressions and Assignment Statements:

Simple expressions : Step count = 1. But if expressions contain function call, step count
is the cost of the invoking functions. This will be large if parameters are passed as call
by value, because value of the actual parameters must assigned to formal parameters.

Assignment statements : General form is <variable> = <expr>. Step count = expr, unless
size of <variable> is a function of instance characteristics. eg., a = b, where a and b are
structures. In that case, Step count = size of <variable> + size of < expr >

4. Iterative Statements:

While <expr> do
Do .. While <expr>
Page 13
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Step count = Number of step count assignable to <expr>

For (<init-stmt>; <expr1>; <expr2>)

Step count = 1, unless the <init-stmt>, <expr1>,<expr2> are function of instance
characteristics. If so, first execution of control part has step count as sum of count of
<init-stmt> and <expr1>. For remaining executions, control part has step count as sum
of count of <expr1> and <expr2>.

5. Switch Statements:
Switch (<expr>) {
Case cond1 : <statement1>
Case cond2 : <statement2>
.
.
Default : <statement>
}

Switch (<expr>) has step count = cost of <expr>

Cost of Cond statements is its cost plus cost of all preceding statements.

6. If-else Statements:
If (<expr>) <statement1>;
Else <statement2>;
Step count of If and Else is the cost of <expr>.

7. Function invocation:
All function invocation has Step count = 1, unless it has parameters passed as called by
value which depend s on instance characteristics. If so, Step count is the sum of the size
of these values.
If function being invoked is recursive, consider the local variables also.

8. Memory management Statements:

new object, delete object, sizeof(object), Step count =1.

9. Function Statements:
Step count = 0, cost is already assigned to invoking statements.

10. Jump Statements:

continue, break, goto has Step count =1
return <expr>: Step count =1, if no expr which is a function of instance characteristics.
If there is, consider its cost also.

Example 1.4
Refer Program 1.2
Introducing a counter for each executable line we can rewrite the program as

int Radd (int a[], int n)

{
count++ // if
If (n>0)
Page 14
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

{
count++ // return
return Radd (a, n-1) + a[n-1];
}
else
{
count++ // return
return 0;
}
}
Case 1: n=0
tRadd = 2

Case 2: n>0
2 + tRadd (n-1)
= 2 + 2 + tRadd (n-2)
= 2 * 2 + tRadd (n-2)
.
.
= 2n + tRadd (0)
= 2n + 2

Example 1.5
Program 1.4
int Madd (int a[][], int b[][], int c[][], int n)
1 {
2 For (int i=0; i<m; i++)
3 For (int j=0; j<n; j++)
4 c[i][j] = a[i][j] + b[i][j];
5 }

Introducing a counter for each executable line we can rewrite the program as
int Madd (int a[][], int b[][], int c[][], int n)
{
For (int i=0; i<m; i++)
{
count++ //for i
For (int j=0; j<n; j++)
{
count++ //for j
c[i][j] = a[i][j] + b[i][j];
count++ //for assignment
}
count++ //for last j
}
count++ //for last i
}
Step count is 2mn + 2m +1.

Page 15
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Step count does not reflect the complexity of statement. It is reflected in step per
execution (s/e).

Refer Program 1.2

Lin s/e Frequenc Total Steps
e y
n=0 n>0 n=0 n>0
1 0 1 1 0 0
2 1 1 1 1 1
3 1 + tRadd (n-1) 0 1 0 1 + tRadd (n-1)
4 0 1 0 0 0
5 1 1 0 1 0
Total no. of steps 2 2 + tRadd (n-1)

Refer Program 1.3

Lin s/e Frequenc Total Steps
e y
1 0 1 0
2 1 1 1
3 1 n+1 n+1
4 1 n n
5 1 1 1
6 0 1 0
Total no. of steps 2n + 3

Refer Program 1.4

Lin s/e Frequenc Total Steps
e y
1 0 1 0
2 1 m+1 m+1
3 1 m(n+1) m(n+1)
4 1 mn mn
5 0 1 0
Total no. of steps 2mn + 2m + 1

2.5. Asymptotic Notations

Step count is to compare time complexity of two programs that compute same function
and also to predict the growth in run time as instance characteristics changes.
Determining exact step count is difficult and not necessary also. Since the values are not
exact quantities we need only comparative statements like c1n2 ≤ tp(n) ≤ c2n2.

For example, consider two programs with complexities c1n2 + c2n and c3n respectively.
For small values of n, complexity depend upon values of c 1, c2 and c3. But there will also
be an n beyond which complexity of c3n is better than that of c1n2 + c2n.This value of n is
called break-even point. If this point is zero, c3n is always faster (or at least as fast).
Common asymptotic functions are given below.

Page 16
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Function Name
1 Constant
log n Logarithmic
n Linear
n log n n log n
n2 Quadratic
n3 Cubic
2n Exponential
n! Factorial

2.5.1. Big ‘Oh’ Notation (O)

O(g(n)) = { f(n) : there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n
≥ n0 }
It is the upper bound of any function. Hence it denotes the worse case complexity of any
algorithm. We can represent it graphically as

Find the Big ‘Oh’ for the following functions:

Linear Functions
Example 1.6
f(n) = 3n + 2

General form is f(n) ≤ cg(n)

When n ≥ 2, 3n + 2 ≤ 3n + n = 4n
Hence f(n) = O(n), here c = 4 and n0 = 2

When n ≥ 1, 3n + 2 ≤ 3n + 2n = 5n
Hence f(n) = O(n), here c = 5 and n0 = 1

Hence we can have different c,n0 pairs satisfying for a given function.

Example 1.7
f(n) = 3n + 3
When n ≥ 3, 3n + 3 ≤ 3n + n = 4n
Hence f(n) = O(n), here c = 4 and n0 = 3

Page 17
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 1.8
f(n) = 100n + 6
When n ≥ 6, 100n + 6 ≤ 100n + n = 101n
Hence f(n) = O(n), here c = 101 and n0 = 6

Quadratic Functions
Example 1.9
f(n) = 10n2 + 4n + 2
When n ≥ 2, 10n2 + 4n + 2 ≤ 10n2 + 5n
When n ≥ 5, 5n ≤ n2, 10n2 + 4n + 2 ≤ 10n2 + n2 = 11n2
Hence f(n) = O(n2), here c = 11 and n0 = 5

Example 1.10
f(n) = 1000n2 + 100n - 6
f(n) ≤ 1000n2 + 100n for all values of n.
When n ≥ 100, 5n ≤ n2, f(n) ≤ 1000n2 + n2 = 1001n2
Hence f(n) = O(n2), here c = 1001 and n0 = 100

Exponential Functions
Example 1.11
f(n) = 6*2n + n2
When n ≥ 4, n2 ≤ 2n
So f(n) ≤ 6*2n + 2n = 7*2n
Hence f(n) = O(2n), here c = 7 and n0 = 4

Constant Functions
Example 1.12
f(n) = 10
f(n) = O(1), because f(n) ≤ 10*1

2.5.2. Omega Notation (Ω)

Ω (g(n)) = { f(n) : there exist positive constants c and n 0 such that 0 ≤ cg(n) ≤ f(n) for all
n ≥ n0 }
It is the lower bound of any function. Hence it denotes the best case complexity of any
algorithm. We can represent it graphically as

Page 18
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 1.13
f(n) = 3n + 2
3n + 2 > 3n for all n.
Hence f(n) = Ω(n)
Similarly we can solve all the examples specified under Big ‘Oh’.

2.5.3. Theta Notation (Θ)

Θ(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that c1g(n) ≤f(n) ≤c2g(n)
for all n ≥ n0 }
If f(n) = Θ(g(n)), all values of n right to n0 f(n) lies on or above c1g(n) and on or below
c2g(n). Hence it is asymptotic tight bound for f(n).

Example 1.14
f(n) = 3n + 2
f(n) = Θ(n) because f(n) = O(n) , n ≥ 2.
Similarly we can solve all examples specified under Big’Oh’.

2.5.4. Little ‘Oh’ Notation (o)

o(g(n)) = { f(n) : for any positive constants c > 0, there exists n 0>0, such that 0 ≤ f(n) <
cg(n) for all n ≥ n0 }
It defines the asymptotic tight upper bound. Main difference with Big Oh is that Big Oh
defines for some constants c by Little Oh defines for all constants.

2.5.5. Little Omega (ω)

ω(g(n)) = { f(n) : for any positive constants c>0 and n0>0 such that 0 ≤ cg(n) < f(n) for
all n ≥ n0 }
It defines the asymptotic tight lower bound. Main difference with Ω is that, ω defines for
some constants c by ω defines for all constants.

Page 19
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

3. The divide-and-conquer approach

Many useful algorithms are recursive in structure: to solve a given problem, they call
themselves recursively one or more times to deal with closely related subproblems.
These algorithms typically follow a divide-and-conquer approach: they break the
problem into several subproblems that are similar to the original problem but smaller
in size, solve the subproblems recursively, and then combine these solutions to create a
solution to the original problem.
The divide-and-conquer paradigm involves three steps at each level of the recursion:
Divide the problem into a number of subproblems that are smaller instances of the
same problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are
small enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.
The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively,
it operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n=2
elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

The following are some standard algorithms that follows Divide and Conquer algorithm.
1. Binary Search is a searching algorithm. In each step, the algorithm compares the
input element x with the value of the middle element in array. If the values
match, return the index of the middle. Otherwise, if x is less than the middle
element, then the algorithm recurs for left side of middle element, else recurs for
the right side of the middle element.
2. Quicksort is a sorting algorithm. The algorithm picks a pivot element,
rearranges the array elements in such a way that all elements smaller than the
picked pivot element move to left side of pivot, and all greater elements move to
right side. Finally, the algorithm recursively sorts the subarrays on left and right
of pivot element.
3. Merge Sort is also a sorting algorithm. The algorithm divides the array in two
halves, recursively sorts them and finally merges the two sorted halves.
4. Closest Pair of Points The problem is to find the closest pair of points in a set of
points in x-y plane. The problem can be solved in O(n^2) time by calculating
distances of every pair of points and comparing the distances to find the
minimum. The Divide and Conquer algorithm solves the problem in O(nLogn)
time.
5. Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A
simple method to multiply two matrices need 3 nested loops and is O(n^3).
Strassen’s algorithm multiplies two matrices in O(n^2.8974) time.
6. Cooley–Tukey Fast Fourier Transform (FFT) algorithm is the most common
algorithm for FFT. It is a divide and conquer algorithm which works in O(nlogn)
time.
7. Karatsuba algorithm for fast multiplication it does multiplication of two n-
digit numbers in at most single-digit multiplications in
general (and exactly when n is a power of 2). It is therefore faster than
the classical algorithm, which requires n2 single-digit products. If n = 210 = 1024,

Page 20
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

in particular, the exact counts are 3 10 = 59, 049 and (210)2 = 1, 048, 576,
respectively.

3.1. Divide And Conquer algorithm

DAC(a, i, j)
{
if(small(a, i, j))
return(Solution(a, i, j))
else
m = divide(a, i, j) // f1(n)
b = DAC(a, i, mid) // T(n/2)
c = DAC(a, mid+1, j) // T(n/2)
d = combine(b, c) // f2(n)
return(d)
}

3.2. Recurrence Relation for DAC algorithm :

This is recurrence relation for above program.
O(1) if n is small
T(n) = f1(n) + 2T(n/2) + f2(n)

Example:
To find the maximum and minimum element in a given array.
Input: { 70, 250, 50, 80, 140, 12, 14 }
Output: The minimum number in a given array is : 12
The maximum number in a given array is : 250
Approach: To find the maximum and minimum element from a given array is an
application for divide and conquer. In this problem, we will find the maximum and
minimum elements in a given array. In this problem, we are using a divide and conquer
approach(DAC) which has three steps divide, conquer and combine.
 For Maximum:
In this problem, we are using the recursive approach to find maximum where we will
see that only two elements are left and then we can easily using condition i.e.
if(a[index]>a[index+1].)
In a program line a[index] and a[index+1])condition will ensure only two elements in
left.
if(index >= l-2)
{
if(a[index]>a[index+1])
{
// (a[index]
// Now, we can say that the last element will be maximum in a given array.
}
else
{
//(a[index+1]
// Now, we can say that last element will be maximum in a given array.
}
}

Page 21
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

In the above condition, we have checked the left side condition to find out the
maximum. Now, we will see the right side condition to find the maximum.
Recursive function to check the right side at the current index of an array.
max = DAC_Max(a, index+1, l);
// Recursive call
Now, we will compare the condition and check the right side at the current index of a
given array.
In the given program, we are going to implement this logic to check the condition on the
right side at the current index.
// Right element will be maximum.
if(a[index]>max)
return a[index];
// max will be maximum element in a given array.
else
return max;
}
 For Minimum:
In this problem, we are going to implement the recursive approach to find the minimum
no. in a given array.
int DAC_Min(int a[], int index, int l)
//Recursive call function to find the minimum no. in a given array.
if(index >= l-2)
// to check the condition that there will be two-element in the left then we can easily find
the minimum element in a given array.
{
// here we will check the condition
if(a[index]<a[index+1])
return a[index];
else
return a[index+1];
}
Now, we will check the condition on the right side in a given array.
// Recursive call for the right side in the given array.
min = DAC_Min(a, index+1, l);
Now, we will check the condition to find the minimum on the right side.
// Right element will be minimum
if(a[index]<min)
return a[index];
// Here min will be minimum in a given array.
else
return min;
Implementation:
// Code to demonstrate Divide and
// Conquer Algorithm
#include <stdio.h>
int DAC_Max(int a[], int index, int l);
int DAC_Min(int a[], int index, int l);

// function to find the maximum no.

// in a given array.
Page 22
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

int DAC_Max(int a[], int index, int l)

{
int max;
if (index >= l - 2) {
if (a[index] > a[index + 1])
return a[index];
else
return a[index + 1];
}

// logic to find the Maximum element

// in the given array.
max = DAC_Max(a, index + 1, l);
if (a[index] > max)
return a[index];
else
return max;
}

// Function to find the minimum no.

// in a given array.
int DAC_Min(int a[], int index, int l)
{
int min;
if (index >= l - 2) {
if (a[index] < a[index + 1])
return a[index];
else
return a[index + 1];
}

// Logic to find the Minimum element

// in the given array.
min = DAC_Min(a, index + 1, l);

if (a[index] < min)

return a[index];
else
return min;
}

// Driver Code
int main()
{
// Defining the variables
int min, max, N;

// Initializing the array

int a[7] = { 70, 250, 50, 80, 140, 12, 14 };

Page 23
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

// recursion - DAC_Max function called

max = DAC_Max(a, 0, 7);

// recursion - DAC_Max function called

min = DAC_Min(a, 0, 7);
printf("The minimum number in a given array is : %d\n", min);
printf("The maximum number in a given array is : %d", max);
return 0;
}

Output:
The minimum number in a given array is : 12
The maximum number in a given array is : 250

Divide and Conquer (alternate introduction)

Divide and conquer (D&C) is an important algorithm design paradigm. It works by

recursively breaking down a problem into two or more sub-problems of the same (or
related) type, until these become simple enough to be solved directly. The solutions to
the sub-problems are then combined to give a solution to the original problem. A divide
and conquer algorithm is closely tied to a type of recurrence relation between functions
of the data in question; data is "divided" into smaller portions and the result calculated
thence.

Steps
 Splits the input with size n into k distinct sub problems 1 < k ≤ n
 Solve sub problems
 Combine sub problem solutions to get solution of the whole problem. Often
sub problems will be of same type as main problem. Hence solutions can be
expressed as recursive algorithms

Control Abstraction
Control abstraction is a procedure whose flow of control is clear but primary
operations are specified by other functions whose precise meaning is undefined

DAndC (P)
{
if Small(P) return S(P);
else
{
divide P into smaller instances P1, P2,…,Pk k1;
apply DandC to each of these sub problems;
retun Combine(DandC(P1), DandC(P2),…,DandC(Pk));
}
}

The recurrence relation for the algorithm is given by

Page 24
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

g(n) – time to computer answer directly from small inputs.

f(n) – time for dividing P and combining solution to sub problems

3.2.1. Binary Search

Problem: Given a list of n sorted elements ai, 1≤ i ≤ n sorted in ascending order. Check
whether an element x is present in the list or not. If present, find the position of x in the
list else return zero

Program
int BinSearch (int a[], int n, int x)
{
int low=1, high=n, mid;
while (low <= high)
{
mid = (low + high)/2;
if (x < a[mid])
high = mid – 1;
else if (x > a[mid])
low = mid + 1;
else
return (mid);
}
return (0);
}

An instance of the problem can be represented as

P = (n, ai,….,al, x)
where n : no of elements
ai,….,al: elements in the list
x : number to be searched

Comparing the program with the Divide and Conquer control abstraction,
S(P) : Index of the element, if the element is present else it will return zero.
g(1) : Θ(1)
If P has more than one element, divide the problem into sub problems as given below
 Pick an index 1 in the range [i, l]
 Compare x with aq
- x = aq, solved
- x < aq, search x in sub list ai, ai+1, … , aq-1 . Then P = (q-i, ai,….,aq-1, x)
- x > aq, search x in sub list aq+1, aq+2, … , al . Then P = (l-q, aq+1,….,al, x)

Time to divide P into one new sub problem is Θ(1). q is selected such that

q= . Answer to new sub problem is answer to P. Hence function Combine is

not needed here.

Page 25
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Simulation

Consider 10 elements 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Number of comparison needed to search element is as per the table given below
Position 1 2 3 4 5 6 7 8 9 10
Element 10 20 30 40 50 60 70 80 90 100
No. of comparisons 3 2 3 4 1 3 4 2 3 4
required

The search tree for the above list of elements will be as given below.

If the element is present, then search end in a circular node (inner node), if the element
is not present, then it end up in a square node (leaf node)
Now we will consider the worse case, average case and best case complexities of the
algorithm for a successful and an unsuccessful search.

Worse Case
Find out k, such that 2k-1 <= n <= 2k
Then for a successful search, it will end up in either of the k inner nodes. Hence the
complexity is O(k), which is equal to O(log2n).
For an unsuccessful search, it need either k-1 or k comparisons. Hence complexity is
Θ (k), which is equal to Θ(log2n).

Average Case
Let I and E represent the sum of distance of all internal nodes from root and sum of
distance of all external nodes from the root respectively. Then
E = I + 2n

Let As(n) and Au(n) represents average case complexity of a successful and unsuccessful
search respectively. Then
As(n) = 1 + I/n
Au(n) = E / (n+1)

As(n) = 1 + I/n
Page 26
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

= 1 + (E-2n)/n
= 1 + (Au(n)(n+1) – 2n)/n
= (n + (Au(n)(n+1) – 2n))/n
= (n(Au(n) -1) + Au(n))/n
= Au(n) – 1 + Au(n)/n
As(n) = Au(n)(1+1/n) - 1

As(n) and Au(n) are directly related and are proportional to log2n.
Hence the average case complexity for a successful and unsuccessful search is O(log 2n)

Best Case
Best case for a successful search is when there is only one comparison, that is at middle
position if there is more than one element. Hence complexity is Θ(1)
Best case for an unsuccessful search is O(log 2n)
Best Case Average Case Worse Case
Successful Θ(1) O(log2n) O(log2n)
Unsuccessful O(log2n) O(log2n) O(log2n)

3.2.2. Maximum and Minimum

Problem: Given a list of n elements ai, 1≤ i ≤ n, find the maximum and the minimum
element from the list

Given below is a straight forward method to calculate the maximum and minimum from
the list of n elements.

Program
Void StraightMinMax (int a[], int n, int *max, int *min)
{
int i;
*max = a[0];
*min = a[0];
for (i=1; i<n; i++)
{
if (a[i] > *max) *max = a[i];
if (a[i] < *min) *min = a[i];
}
}

Let us calculate the time complexity of the algorithm. Here, only element comparisons
are considered, because the frequency counts of other operations are same as that of
element comparison. 2(n-1) comparisons are required for worse, average and best case.
But if we modify the code as

if(a[i] > *max) *max = a[i];

else if (a[i]<min) *min = a[i];

Page 27
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Then Best case complexity is (n-1), it happens when elements are sorted in increasing
order.
Worse case complexity is 2(n-1), when elements are sorted in decreasing order
Average case complexity is (2(n-1)+ (n-1))/2 = 3(n-1)/2

Now let us solve the problem using Divide and Conquer method. An instance of the
problem can be represented as
P = (n, a[i],….,a[j])
where n : no of elements
a[i],….,a[j]: elements in the list

When n=1, max = min = a[1]. When n=2, the problem can be solved in one comparison.
Hence, Small(P) is true when n<=2. If there are more elements, then we have to divide
the problem into sub problems. So divide the problem into two instances,

To solve the problem, invoke Divide and Conquer algorithm recursively. Combine
solution for P1 and P2. Set Max(P) as larger among Max(P1) and Max(P2) and Min(P)
as smaller among Min(P1) and Min(P2)

Program
Void MaxMin (int i, int j, int *max, int *min)
{
if (i==j)
{
*max = a[i];
*min = a[i];
}
else if (i == j-1)
{
if (a[i] < a[j])
{
*max = a[j];
*min = a[i];

}
else
{
*max = a[i];
*min = a[j];

}
}
else
{
mid = (i+j)/2;
MaxMin (i, mid, *max, *min);
MaxMin (mid+1, j, *max1, *min1);
if (*max < *max1) *max = *max1;
if (*min > *min1) *min = *min1;

Page 28
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

}
}

Example
Consider 9 elements 22, 13, -5, -8, 15, 60, 17, 31 and 47. The recursive call can be
represented using a tree as given below

This can be represented by recurrence relation as

If n is a power of two, n = 2k
T(n) = 2T(n/2) + 2
= 2 (2T(n/4) + 2) + 2
= 4T(n/4) + 4 + 2
= ...

= 2k-1+ 2k -2
= 2k-1+ n -2
= n/2 + n – 2
T(n) = 3n/2 – 2 (Best, average, Worst)
Comparing with the Straight forward method, Divide and Conquer is 50% more faster.
But additional stack space is required for recursion.

Yet another figures are obtained if we include position comparison also, while
calculating complexity. For this rewrite Small(P) as
if (i >= j-1) (Small(P)}

Page 29
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

C(n) = 2C(n/2) + 3
= 4C(n/4) + 6 + 3
= 4C(n/4) + 3(1+2)
= ...

= 2k-1.2 + 3[2k-1-2]
= 2k + 3.2k-1-3
= n + 3.n/2 – 3
C(n) = 5n/2 – 3
While using StraightMinMax the comparison is 3(n-1) which is greater than 5n/2–3.
Even though the element comparison is less for MaxMin, it is slower than normal
method because of the stack.
Binary Search
Given a sorted array arr[] of n elements, write a function to search a given element x in
arr[].
A simple approach is to do linear search.The time complexity of above algorithm is O(n).
Another approach to perform the same task is using Binary Search.

Example :

The idea of binary search is to use the information that the array is sorted and reduce
the time complexity to O(Log n).
Recommended: Please solve it on “PRACTICE ” first, before moving on to the
solution.

Page 30
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

We basically ignore half of the elements just after one comparison.

1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray
after the mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.
Recursive implementation of Binary Search

// C program to implement recursive Binary Search

#include <stdio.h>

// A recursive binary search function. It returns

// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

// If the element is present at the middle

// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present

// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not

// present in array
return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
Page 31
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Output :
Element is present at index 3

Example
1 2 3 4 5 6 7 8 9 10
2 5 8 12 16 23 38 56 72 91

Case 1: Searching the key elements 16

Value = a[mid]
Value = 16
Low = 1, high=10 mid= (1+10)/2=5
Mid value and key value to be equal.

Searching the key elements 23

Case 2:
Value > a [mid]
Value = 23
Low = 1, high=10 mid= (1+10)/2=5
Key value is found the right side of mid value, so low=mid+1
Low = mid+1=5+1=6
Low = 6, high=10 mid=(10+6)/2=8
Case 3:
Value < a [mid]
Key value is found the left side of mid value, so high=mid-1
Low = 6, high=mid – 1= 8-1=7
Low = 6, high=7, mid = (6+7)/2=6
The mid value and key value to be equal in a [6], then return the key value is a [6] =23.
6.3 Complexity Analysis of Binary Search
Best Case Time Complexity – O (1)
Worst Case Time Complexity – O (log n)
Average Case Time Complexity – O (log n)

3.2.3. Merge Sort

Given a sequence of n elements a[1],...,a[n].
Spilt into two sets
Each set is individually sorted, resultant is merged to form sorted list of n elements
Program

Page 32
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 2.2
Consider 10 elements 310, 285, 179, 652, 351, 423, 861, 254, 450 and 520. The
recursive call can be represented using a tree as given below

The recurrence relation for the algorithm can be written as

Page 33
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

When n is power of 2, we can write n = 2k

T(n) = 2(T(n/4) + cn/2) + cn
= 4T(n/4) + 2cn
= 4(2T(n/8) + cn/4) + 2cn
=…
= 2kT(1) + kcn
T(n) = an + cnlogn
If 2k<n≤2k+1 , T(n)≤T(2k+1)
Hence T(n) = O(nlogn)

3.2.4. Quick Sort

Given a sequence of n elements a[1],...,a[n].
Divide the list into two sub arrays and sorted so that the sorted sub arrays need not be
merged later. This is done by rearranging elements in the array such that a[i]<=a[j] for
1≤i≤m and m+1≤j≤n, 1≤m≤n. Then the elements a[1] to a[m] and a[m+1] to a[n] are
independently sorted, Hence no merging is required.

Pick an element, t=a[s], reorder other elements so that all elements appearing before t is
less than or equal to t, all elements after t is greater than or equal to t.

Program

int partition (int a[], int m, int p)

{
int v=a[m], i=m, j=p ;
do
{
do
i++;
while(a[i]<v);
do
j--;
while(a[j]>v);
if (i<j) interchange(a,i,j);
}
while(i<j);
a[m] = a[j]; a[j] = v; return(j);

Page 34
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

}
While calculating complexity we are considering element comparison alone. Assume
that n elements are distinct and the distribution is such that there is equal probability
for any element to get selected for partitioning.

Worse case complexity

According to the previous program the number of elements is at most p-m+1.
Let the total number of elements in all call of Partition at a level be r.
At level one there is only one call of Partition, hence r=n
At level two, there is at most two calls, hence r=n-1.
Hence we can tell, at all levels the complexity is O(R), where the value of r is diminishing
at each level.
The worse case complexity Cw(n) is the sum of r at each level, hence Cw(n) = O(n2)
Average case complexity
The partitioning element has equal probability of becoming the i th smallest element,
1≤ i≤ p-m in the array a[m:p-1].
Hence probability for sub arrays being sorted, a[m:j], a[j+1:p-1]is 1/(p-m), m≤j<p.

Page 35
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example

Illustration of partition() :
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6

low = 0, high = 6, pivot = arr[h] = 70

Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1

j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i=0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same

j = 1 : Since arr[j] > pivot, do nothing

// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

i=1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30

j = 3 : Since arr[j] > pivot, do nothing

// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])

i=2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i=3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped
Page 36
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

We come out of loop because j is now equal to high-1.

Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped

Now 70 is at its correct place. All elements smaller than

70 are before it and all elements greater than 70 are after it.

Example

Page 37
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Page 38
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

4. Recurrence Methods

Recurrence is an equation or inequality that describes a function in terms of its value on

smaller inputs, and one or more base cases
e.g., recurrence for Merge-Sort

(1) if n = 1
T(n)  

2T(n/2) + (n) if n > 1

• Useful for analyzing recurrent algorithms

• Make it easier to compare the complexity of two algorithms
• Methods for solving recurrences
– Substitution method
– Recursion tree method
– Master method
– Iteration method
4.1. Substitution Method
 Use mathematical induction to derive an answer
 Derive a function of n (or other variables used to express the size
of the problem) that is not a recurrence so we can establish an
upper and/or lower bound on the recurrence
 May get an exact solution or may just get upper or lower bounds
on the solution

Steps
 Guess the form of the solution
 Use mathematical induction to find constants or show that they can be found and
to prove that the answer is correct

Example 1.15
Find the upper bound for the recurrence relation
T(n) = 2 T( n/2 ) + n

Guess the solution as T(n) = O(n.lg(n))

Then T(n) = c.n.lgn
Substituting in T(n), we get
T(n) =
= c n lg(n/2) + n
= cn lg(n) – cnlg(2) + n
= cn lg(n) – cn + n
= cn lg(n), c >=1
To prove using mathematical induction, we have to show that the solution holds for
boundary condition also. We select boundary condition as n>=2 (Because for n = 1,
T(1) = c.1.lg(1) = 0 which is false according to the definition of T(n))

Example 1.16
Find the worse case complexity of Binary Search

Page 39
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

T(n) = c + T(n/2)

• Guess: T(n) = O(lgn)

– Induction goal: T(n) ≤ d lgn, for some d and n ≥ n0
– Induction hypothesis: T(n/2) ≤ d lg(n/2)
• Proof of induction goal:
T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
if: – d + c ≤ 0, d ≥ c

Example 1.17
T(n) = T(n-1) + n

• Guess: T(n) = O(n2)

– Induction goal: T(n) ≤ c n2, for some c and n ≥ n0
– Induction hypothesis: T(n-1) ≤ c(n-1)2 for all k < n
• Proof of induction goal:
T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
if: 2cn – c – n ≥ 0  c ≥ n/(2n-1)  c ≥ 1/(2 – 1/n)
– For n ≥ 1  2 – 1/n ≥ 1  any c ≥ 1 will work

Example 1.17
T(n) = 2T(n/2) + n
• Guess: T(n) = O(nlgn)
– Induction goal: T(n) ≤ cn lgn, for some c and n ≥ n0
– Induction hypothesis: T(n/2) ≤ cn/2 lg(n/2)
• Proof of induction goal:
T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
if: - cn + n ≤ 0  c ≥ 1

4.2. Recursion Tree Method

 Main disadvantage of Substitution method is that it is always difficult to come
up with a good guess
 Recursion tree method allows you make a good guess for the substitution
method
 Allows to visualize the process of iterating the recurrence

Steps
 Convert the recurrence into a tree.
 Each node represents the cost of a single sub problem somewhere in the set of
recursive function invocations
 Sum the costs within each level of the tree to obtain a set of per-level costs
 Sum all the per-level costs to determine the total cost of all levels of the recursion

Page 40
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 1.18
T(n) = 3T(n/4) + (n2)
T(n) = 3T(n/4) + cn2

• The sub problem size for a node at depth i is n/4i

– When the sub problem size is 1, n/4i = 1, i=log4n
– The tree has log4n+1 levels (0, 1, 2,.., log4n)
• The cost at each level of the tree (0, 1, 2,.., log4n-1)
– Number of nodes at depth i is 3i
– Each node at depth i has a cost of c(n/4i)2
– The total cost over all nodes at depth i is 3i c(n/4i)2=(3/16)icn2
• The cost at depth log4n
– Number of nodes is 3log4 n  nlog4 3
– Each contributing cost T(1)

The total cost nlog4 3T (1)  (nlog4 3 )

3 2 3 3
T (n)  cn 2  cn  ( ) 2 cn 2  ...  ( ) log4 n 1 cn 2  (n log4 3 )
16 16 16
log4 n 1
3 i 2
 
i 0
(
16
) cn  (n log4 3 )

3 i 2
 ( ) cn  (n log4 3 )
i 0 16
1 16 2
 cn 2  (n log4 3 )  cn  (n log4 3 )
3 13
1
16
 O(n 2 )

Prove T(n)=O(n2) is an upper bound by the substitution method

T(n)  dn2 for some constant d > 0

T ( n)  3T ( n / 4)  cn 2
 3d n / 4  cn 2
2

 3d ( n / 4) 2  cn 2
3
 dn 2  cn 2
16
 dn 2 Page 41
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 1.19

W(n) = 2W(n/2) + (n2)

• Subproblem size at level i is: n/2i

• Subproblem size hits 1 when 1 = n/2i  i = lgn
• Cost of the problem at level i = (n/2i)2 No. of nodes at level i = 2i
• Total cost:

lg n 1 lg n 1  i i
n2 1 1 1
W (n)   i  2 W (1)  n     n  n 2     O(n) n 2
lg n 2
 O ( n )  2n 2
i 0 2 i 0  2  i 0  2  1 1
2

 W(n) = O(n2)

log3 / 2 n log3 / 2 n
lg n 1
n  n  ...  n  n
i 0
 1  n log
i 0
3/ 2 nn 
lg 3 / 2 lg 3 / 2
n lg n

 W(n) = O(nlgn)

Page 42
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Example 1.20
W(n) = W(n/3) + W(2n/3) + O(n)

• The longest path from the root to a leaf is: n  (2/3)n  (2/3)2 n  …  1
• Subproblem size hits 1 when 1 = (2/3)in  i=log3/2n
• Cost of the problem at level i = n
• Total cost:

Example 1.21

T(n) = T(n/4) + T(n/2) + n2

Page 43
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

4.3. Master Method

 The master method applies to recurrences of the form T(n) = a T(n/b) + f (n) ,

where a  1, b > 1, and f is asymptotically positive.

 Describe the running time of an algorithm that divides a problem of size n into a sub
problems, each of size n/b

Page 44
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

 There are three common cases

Case 1

 Compare f (n) with nlogba

 If f (n) = O(nlogba – e) for some constant e > 0.

i.e., f (n) grows polynomially slower than nlogba

i.e., f(n) is asymptotically smaller by an ne factor.

Then Solution: T(n) = Θ(nlogba) .

Page 45
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Case 2

 Compare f (n) with nlogba

 If f (n) = Θ (nlogba)

i.e., f (n) and nlogba grow at similar rates.

Then Solution: T(n) = Θ(nlogba lgn) .

Page 46
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

Case 3

 Compare f (n) with nlogba

 If f (n) = Ω(nlogba+e) for some constant e > 0

i.e., f (n) grows polynomially faster than nlogba

i.e., f(n) is asymptotically larger by an ne factor.

Then Solution: T(n) = Θ(f(n)) .

Example 1.22

T(n)=9T(n/3) + n

a=9, b=3, f(n) = n

CASE 1: nlogb a  nlog3 9  (n 2 ), f (n)  O(nlog3 91 )

T(n) = (n2)

Example 1.23

T(n) = 4T(n/2) + n

a = 4, b = 2  nlogba = n2; f (n) = n.

CASE 1: f (n) = O(n2 – e) for e = 1.

Page 47
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

 T(n) = Θ(n2).

Example 1.24

T(n) = T(2n/3) + 1

a=1, b=3/2, f(n)=1

nlogb a  nlog3 / 2 1  1, f (n)  1  (1)
Case 2:

T(n) = (lg n)

Example 1.25

T(n) = 4T(n/2) + n2

a = 4, b = 2  nlogba = n2; f (n) = n2.

CASE 2: f (n) = Q(n2lg0n), that is, k = 0.

 T(n) = Θ(n2lg n).

Example 1.26

T(n) = 3T(n/4) + n lg n (Case 3)

a=3, b=4, f(n) = n lg n

Case3:logb a
n  nlog4 3  O(n0.793) f (n)  (nlog4e3= )0.2

For sufficiently large n, af(n/b) = 3(n/4)lg(n/4)  (3/4)n lg n=cf(n) for c=3/4

T(n) = (n lg n)

Example 1.27

T(n) = 4T(n/2) + n3

a = 4, b = 2  nlogba = n2; f (n) = n3.

CASE 3: f (n) = Ω(n2 + e) for e = 1 and 4(cn/2)3 £ cn3 (reg. cond.) for c = 1/2.

 T(n) = Θ(n3).

Page 48
 [DESIGN & ANALYSIS OF ALGORITHM]
CENTRAL UNIVERSITY OF KASHMIR Unit I

5. Exercises
From reference 1 in references Section 6.
Exercise numbers: 4.4-1 4.4-2 4.4-3 4.4-4 4.4-5 4.4-6 4.4-7 4.4-8
4.4-9 4.5-1 4.5-2 4.5-3 4.5-4
4-1 Recurrence examples: a, b, c, d, e, f, g.
4-3 More recurrence examples : a, b, c, d, f, e, f, g, h, i, j.
7.2-2 7.2-3 7.2-4 7.2-5

6. References
1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, “Introduction to
Algorithms”, 2nd Ed., PHI.
2. Ellis Horowitz and Sartaz Sahani, “Computer Algorithms”, Galgotia Publications.
3. V. Aho, J. E. Hopcroft, J. D. Ullman, “The Design and Analysis of Computer
Algorithms”, Addition Wesley.
4. D. E. Knuth, “The Art of Computer Programming”, 2nd Ed., Addison Wesley.

Page 49