Design and Analysis of
Algorithms
Unit - I
Periyar Govt. Arts College
Cuddalore
Dr. R. Bhuvaneswari
Assistant Professor
Department of Computer Science
Periyar Govt. Arts College, Cuddalore.
1 Dr. R. Bhuvaneswari
Introduction to the Concept of Algorithms
Syllabus
UNIT-I
Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations –
Conditional asymptotic notation – Removing condition from the
conditional asymptotic notation - Properties of big-Oh notation –
Recurrence equations – Solving recurrence equations – Analysis of
linear search.
Text Book:
K.S. Easwarakumar, Object Oriented Data Structures using C++,
Vikas Publishing House pvt. Ltd., 2000 (For Unit I)
Periyar Govt. Arts College
2 Cuddalore
Dr. R. Bhuvaneswari
Introduction to the Concept of Algorithms
• Algorithm
• Problem Solving
• Design of an Algorithm
• Analysis of an algorithm
Periyar Govt. Arts College
3 Cuddalore
Dr. R. Bhuvaneswari
Notion of an Algorithm
Problem
Algorithm
Input Computer Output
Periyar Govt. Arts College
4 Cuddalore
Dr. R. Bhuvaneswari
Algorithm
• An algorithm is a finite set of instructions that, if followed,
accomplishes a particular task i.e., for obtaining a required
output for any legitimate input in a finite amount of time.
• All algorithms must satisfy the following criteria:
Definiteness. Each instruction is clear and unambiguous.
Effectiveness. Every instruction must be very basic so that it
can carried out, by a person using pencil and paper.
Finiteness. If we trace out the instructions of an algorithm,
then for all cases, the algorithm terminates after a finite
number of steps.
Input. Zero or more quantities are externally supplied.
Output. At least one quantity is produced.
Periyar Govt. Arts College
5 Cuddalore
Dr. R. Bhuvaneswari
Algorithm Specification
1. Input two numbers
• An algorithm can be described in 2. Add the two numbers
three ways: 3. Print the result
Natural language in English
Graphic representation called
flowchart
Pseudo-code method
In this method we typically
represent algorithms as
program, which resembles C
language
Periyar Govt. Arts College
6 Cuddalore
Dr. R. Bhuvaneswari
Pseudo-code Conventions
1. Comments begin with // and continue until the end of line.
2. Blocks are indicated with matching braces { and }.
3. An identifier begins with a letter. The data types of
variables are not explicitly declared.
4. Assignment of values to variables is done using the
assignment statement.
‹variable› := ‹expression›;
5. There are two Boolean values true and false.
Logical operators: AND, OR, NOT
Relational operators: , ≤, =, ≠, >, ≥
Periyar Govt. Arts College
7 Cuddalore
Dr. R. Bhuvaneswari
Pseudo-code Conventions
6. The following looping statements are used:
while, for and repeat-until
while loop: for loop: repeat-until:
while ‹condition› do for variable:= value1 to value2 repeat
{ step step-value do ‹statement 1›
‹statement 1› { .
. ‹statement 1› .
. . ‹statement n›
‹statement n› . until ‹condition›
} ‹statement n›
}
Periyar Govt. Arts College
8 Cuddalore
Dr. R. Bhuvaneswari
Pseudo-code Conventions
7. A conditional statement has the following forms:
if ‹condition› then ‹statement›
if ‹condition› then ‹statement 1› else ‹statement 2›
case statement:
case
{
:‹condition 1›: ‹statement 1›
.
.
:‹condition n›: ‹statement n›
:else: ‹statement n+1›
} Periyar Govt. Arts College
9 Cuddalore
Dr. R. Bhuvaneswari
Pseudo-code Conventions
8. Input and output are done using the instructions read and
write.
9. There is only one type of procedure: Algorithm.
Algorithm contains
Heading
Body
The heading takes the form
Algorithm Name (‹parameter list›) heading
{
…… body
……
}
Periyar Govt. Arts College
10 Cuddalore
Dr. R. Bhuvaneswari
Pseudo-code Conventions
1. Algorithm Max(A, n)
2. // A is an array of size n. n = 5, result = 10
3. { A[1] = 10
4. Result := A[1]; A[2] = 87 result = 87
5. for i :=2 to n do A[3] = 45
6. if A[i] > result then A[4] = 66
7. Result := A[i]; A[5] = 99 result = 99
8. return Result;
9. }
Periyar Govt. Arts College
11 Cuddalore
Dr. R. Bhuvaneswari
Algorithm Analysis
Study of algorithm involves three major parts:
• Designing the algorithm
• Proving the correctness of the algorithm
• Analysing the algorithm
Analysing the algorithm deals with
1. Space Complexity
2. Time Complexity
Practically, time and space complexity can be reduced only
to certain levels, as later on reduction of time increases
the space and vice-versa → time-space trade-off.
Periyar Govt. Arts College
12 Cuddalore
Dr. R. Bhuvaneswari
Algorithm Analysis
Method - 1
• An extra array of size n is
int ary1[n]; used
int ary2[n]; • So total space required is 2n
for (int i=0; in; i++) • n assignments are made and
ary2[i] = ary1[(n-1)-i]; the time complexity is n units
of time.
Periyar Govt. Arts College
13 Cuddalore
Dr. R. Bhuvaneswari
Algorithm Analysis
int ary1[n]; • One array of size n and a
int k = floor(n/2); temporary variable temp is
for (int i=0;i<k;i++) used.
swap(&ary1[i],&ary1[(n-1)-i]; • So space occupied is n+1
• Swapping - 3 assignments
swap(int *a, int *b) are required.
{ • Number of times
int temp = *a; performed is half the size
*a = *b; of the array.
*b = *temp; • So the time complexity is
} 3n/2.
Periyar Govt. Arts College
14 Cuddalore
Dr. R. Bhuvaneswari
Asymptotic Notations
• Three standard notations
Big-oh (O) : asymptotic “less than”
F(n) = O(g(n)) implies: f(n) “≤” g(n)
Big omega () : asymptotic “greater than”
F(n) = (g(n)) implies: f(n) “≥” g(n)
Theta () : asymptotic “equality”
F(n) = (g(n)) implies: f(n) “” g(n)
• Time complexity of a function may be one of the following
Periyar Govt. Arts College
15 Cuddalore
Dr. R. Bhuvaneswari
Asymptotic Notations
Big-Oh
The function f(n) = O(g(n)) if and only if there exists positive
constant c and n0 such that f(n) ≤ c*g(n) for every n ≥ n0
Example:
f(n) = 2n+3
1. 2n+3 ≤ 10n for every n ≥ 1
f(n) = O(n)
2. 2n+3 ≤ 2n2 + 3n2
2n+3 ≤ 5n2
f(n) = O(n2)
Periyar Govt. Arts College
16 Cuddalore
Dr. R. Bhuvaneswari
Asymptotic Notations
Omega
The function f(n) = (g(n)) if and only if there exists positive
constant c and n0 such that f(n) ≥ c*g(n) for every n ≥ n0
Example:
f(n) = 2n+3
1. 2n+3 ≥ 1*n for every n ≥ 1
f(n) = (n)
2. 2n+3 ≥ 1*logn
f(n) = (logn)
Periyar Govt. Arts College
17 Cuddalore
Dr. R. Bhuvaneswari
Asymptotic Notations
Theta
The function f(n) = (g(n)) if and only if there exists positive
constant c1, c2 and n0 such that
c1*g(n) ≤ f(n) ≤ c2*g(n) for every n ≥ n0
Example:
f(n) = 2n+3
1*n ≤ 2n+3 ≤ 5*n
f(n) = (n)
Periyar Govt. Arts College
18 Cuddalore
Dr. R. Bhuvaneswari
Properties of big oh(O) notation
1. O(f(n)) + O(g(n)) = O(max{f(n),g(n)})
2. F(n) = O(g(n)) and g(n) ≤ h(n) implies f(n) = O(h(n))
3. Any function can be said as an order of itself. That is, f(n) = O(f(n))
f(n) = 1*f(n)
4. Any constant value is equivalent to O(1). That is, c = O(1)
5. If limn→ {f(n)/g(n)} R > 0 then f(n) (g(n))
R → set of non negative real numbers
6. If limn→ {f(n)/g(n)} = 0 then f(n) O(g(n)) but f(n) (g(n)
7. If limn→ {f(n)/g(n)} = then f(n) (g(n)) but f(n) (g(n)
Periyar Govt. Arts College
19 Cuddalore
Dr. R. Bhuvaneswari
Recurrence Equations
Recurrence equations can be classified into
• Homogeneous recurrence equations
• Inhomogeneous recurrence equations
Suppose T(n) is the time complexity of an algorithm for the input size n.
Assume that T(n) is recursively defined as
T(n) = b1T(n-1) + b2T(n-2) + …… + bkT(n-k)
a0T(n) + a1T(n-1) + …….. + akT(n-k) = 0
Let us denote T(i) as xi
a0xn +a1xn-1 + ……… + akxn-k = 0
which is a homogeneous recurrence equation.
a0xk + a1xk-1 + …….. + ak = 0, n=k
will have k roots. Let the roots be r1, r2, ….. rk.
They may or may not be same. Periyar Govt. Arts College
20 Cuddalore
Dr. R. Bhuvaneswari
Homogeneous Recurrence Equations
Solving homogeneous recurrence equation
Case (i): All roots are distinct
eg. x2-5x+6 = 0
(x-3)(x-2) = 0 => x = 3 and 2
General solution is T(n) = c13n +c22n
Case (ii): Suppose some of p roots are equal and the remaining are
distinct.
eg. (x-2)3(x-3) = 0 => x = 2,2,2,3
General solution is T(n) = C12n + C2n2n + C3n22n + C43n
Periyar Govt. Arts College
21 Cuddalore
Dr. R. Bhuvaneswari
Inhomogeneous Recurrence Equations
A linear non-homogenous recurrence relation with constant
coefficients is a recurrence relation of the form
an = c1an-1 + c2an-2 + … + ckan-k+ f(n)
where c1, c2, …, ck are real numbers, and f(n) is a function
depending only on n.
The recurrence relation
an = c1an-1 + c2an-2 + … + ckan-k,
is called the associated homogeneous recurrence relation.
This recurrence includes k initial conditions.
a0 = C0, a1 = C1 … ak = Ck
Periyar Govt. Arts College
22 Cuddalore
Dr. R. Bhuvaneswari
Inhomogeneous Recurrence Equations
Case (i): Solve the recurrence equation
T(n) – 2T(n-1) = 1 subject to T(0) = 0
n = 0, T(0) = c1 + c2
Proof: The characteristic equation is
ie., c1+ c2 = 0 ------- 1
(x-2)(x-1)=0. Therefore, the roots are 2 and 1.
n =1, T(1) = c1 + 2c2
Now, the general solution is
ie., c1 + 2c2 = 1 ------- 2
T(n) = c11n + c22n from 1, c1 = -c2
Since T(0) = 0, from the given equation T(1) substituting in 2,
will be 1. -c2 + 2c2 = 1 → c2 = 1
Thus, from the general solution we get c1 = -1 from 1, c2 = -c1
and c2 = 1. substituting in 2,
c1 +2(-c1) = 1 → c1 = -1
So,
T(n) = 2n – 1 = (2n)
Periyar Govt. Arts College
23 Cuddalore
Dr. R. Bhuvaneswari
Inhomogeneous Recurrence Equations
Case (ii): Solve the recurrence equation
T(n) = 2T(n-1) + n2n + n2
Proof: The characteristic equation is (x-2)(x-2)2(x-1)3 = 0. That is
(x-2)3(x-1)3 = 0. Therefore, the roots are 2, 2, 2, 1, 1 and 1. Now, the
general solution is
T(n) = c12n + c2n2n + c3n22n+ c41n + c5n1n + c6n21n
Hence, T(n) = O(n22n)
Periyar Govt. Arts College
24 Cuddalore
Dr. R. Bhuvaneswari
Analysis of linear search
• Algorithms are analyzed to get best-case, worst-case and average-
case.
• Each problem is defined on a certain domain
eg. Algorithm to multiply two integers. In this case, the domain
of the problem is a set of integers.
• From the domain, we can derive an instance of the problem.
Any two integers may be an instance to the above problem.
• So, when an algorithm is analyzed, it is necessary that the analyzed
value is satisfiable for all instances of the domain.
• Let Dn be the domain of a problem, where n be the size of the input.
• Let I Dn be an instance of the problem taken from the domain Dn.
• T(I) be the computation time of the algorithm for the instance I Dn
Periyar Govt. Arts College
25 Cuddalore
Dr. R. Bhuvaneswari
Analysis of linear search
Best-case analysis:
This gives the minimum computed time of the algorithm with respect to
all instances from the respective domain.
B(n) = min{T(I) | I Dn}
Worst-case analysis:
This gives the maximum computation time of the algorithm with respect
to all instances from the respective domain.
W(n) = max{T(I) | I Dn}
Average-case analysis:
where p(I) is the average probability with respect to the instance I.
Periyar Govt. Arts College
26 Cuddalore
Dr. R. Bhuvaneswari
Analysis of linear search
int linearsearch(char A[], int size, char ch)
{
for (int i=0; i<size; i++) Location of the Number of
{ element comparisons required
if (A[i] == ch) 0 1
return(i); 1 2
2 3
}
. .
return(-1); . .
} n-1 n
not in the array n
Periyar Govt. Arts College
27 Cuddalore
Dr. R. Bhuvaneswari
Analysis of linear search
B(n) = min{1,2,……, n} = 1
= O(1)
W(n) = max{1, 2, ……., n} = n
= O(n)
Let k be the probability of x being in the array.
Successful search = 1+2+3+….+n = n(n+1)/2
𝑛(𝑛+1)/2 𝑛+1
Average = =
𝑛 2
Probability of unsuccessful search = 1 – k
A(n) = k * (n+1)/2 + (1-k) * n, where n → number of unsuccessful search
Suppose x is in the array, then k = 1. Therefore,
A(n) = (n+1)/2 = O(n)
Periyar Govt. Arts College
28 Cuddalore
Dr. R. Bhuvaneswari
