Design and Analysis of Algorithms (203105301)

ACADEMIC YEAR 2020-21

Notes Unit-1

Algorithm:

The word algorithm comes from the name of a Persian mathematician Abu Ja’far
Mohammed ibn-i Musa al Khowarizmi.

Algorithm is a finite set of instructions used to accomplish particular task.

In computer science, algorithm refers to a special method useable by a computer for solution
of a problem.

An algorithm takes some value or set of values, as input and produces some value, or
set of values, as output.

Algorithm is a tool for solving a well-specified computational problem.

It can be written in a pseudo code which can be implemented in the language of

programmer’s choice.

Characteristics of algorithms

Input: If an algorithm takes inputs, it should be well-defined inputs. What the algorithm
takes in as input, Zero or more quantities supplied.

Output: The algorithm must clearly define what output will be produced and it should be
well-defined. At least one quantity is produced as an output.
Definiteness: All the steps in the algorithm should be defined precisely. Each instruction
should be cleared and unambiguous.

Finiteness: All the steps required in the algorithm should be finite, If we trace out the
instructions of an algorithm, then for all cases, the algorithm terminates after a finite
number of steps. it should not end up in infinite loops.

Effectiveness: each step in the algorithm must be able to be performed in a finite amount of
time. Every instruction must be basic so that it can be carried out in principal by a person
using only pen and pencil.

Non –ambiguous: more than one interpretation should not be generated for single step.

Generality: Algorithm must be applicable to all problems of a similar form.

Correctness: Algorithm should produce an appropriate and correct output for each input
produce.

Efficient: Algorithm should run as quickly as possible, and use as little memory as possible.
 Figure 1 Characteristics of an algorithm

Why Analyse an Algorithm?

More than one algorithm is possible for the same application. For example, we know that
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 change. At same time, we need to calculate the memory space required by
each algorithm.

The efficiency of algorithm is decided by the care-full analysis of algorithm.The analysis of

an algorithm can help us in understanding of solution in better way. Analyse an Algorithm is
Used for predicting the resources that the algorithm requires.

Resources such as memory, communication bandwidth or computer hardware are of

primary concern. But most often it is computational time that we want to measure.

Time & Space analysis are of crucial importance for performance measurement of a
software module.

Order of Growth

Any algorithm is expected to work fast for any input size. For smaller input size any
algorithm will work fine but for higher input size the execution time is much higher.
By increasing the size of input size (n) we can analyze how well our algorithm works. Let
input size, n=5 and we have to sort the list of elements for e.g. 5,9,50,35,2 So for n=5 our
algorithm will work fine but what if n=10000?

So how the behaviour of algorithm changes with the no. of inputs will give the analysis of
the algorithm and it is called as Order of Growth.

Rate of Growth

The rate at which the running time increases as a function of input is called rate of growth.

Figure 2 growth rate

Figure 3 Rate of growth in decreasing order
Types of Analysis

The best, worst and average cases of an algorithm express what the resource usage is at
least, at most and on average, respectively.

The resource being considered is running time, but it could be memory or the other
resource

Figure 4 algorithm analysis

1)Best case

The best case complexity of the algorithm is the function defined by the minimum number
of steps taken on any instance of size n.

Best case is a lower bound on the running time for any input.Minimum time required for
program execution is known as best case.

Best case of an algorithm gives guarantee that the algorithm will take minimum this
amount of time.

2)Average case
The average case is a function defined by the average number of steps taken on any
instance of size n. Average time required for program execution is known as average case
for algorithm.

Average case is a tight bound on the running time for any input.

3)Worst case

The worst case complexity of the algorithm is the function defined by the maximum number
of steps taken on any instance of size n.

Worst case is a upper bound on the running time for any input.Maximum time required for
program execution is known as best case.

Worst case of an algorithm gives guarantee that the algorithm will take maximum this
amount of time.

Asymptotic Complexity

Asymptotic notation gives running time of an algorithm as a function of input size n for large
n.Asymptotic Complexity expressed using only the highest-order term in the expression for
the exact running time. Instead of exact running time, say Q(n2).

The notations describe rate-of-growth relations between the defining function and the
defined set of functions.Asymptotic Complexity describes behavior of function in the limit.

What is Asymptotic Behavior

The word Asymptotic means approaching a value or curve arbitrarily closely (i.e., as some
sort of limit is taken).

Remember studying about Limits in High School, this is the same.

The only difference being, here we do not have to find the value of any expression where n
is approaching any finite number or infinity, but in case of Asymptotic notations, we use the
same model to ignore the constant factors and insignificant parts of an expression, to
device a better way of representing complexities of algorithms, in a single coefficient, so
that comparison between algorithms can be done easily.[1]

Let's take an example to understand this:

If we have two algorithms with the following expressions representing the time required by
them for execution, then:

Expression 1: (2n2 + 30n - 4)

Expression 2: (20n3 + 10n - 2)

Now, as per asymptotic notations, we should just worry about how the function will grow as
the value of n(input) will grow, and that will entirely depend on n2 for the Expression 1, and
on n3 for Expression 2. Hence, we can clearly say that the algorithm for which running time
is represented by the Expression 2, will grow faster than the other one, simply by analyzing
the highest power coefficient and ignoring the other constants(20 in 20n2) and insignificant
parts of the expression(30n - 4 and 10n - 2).

The main idea behind casting aside the less important part is to make things manageable.

All we need to do is, first analyze the algorithm to find out an expression to define it's time
requirements and then analyze how that expression will grow as the input(n) will grow.

Ο Notation

Ο Notation express as the upper bound of an algorithm or worst case of an algorithm.

f(n)=O(g(n)) implies: Ο(g(n)) = { f(n) : there exists positive constants c>0 and n0 such that
f(n) ≤ c.g(n) for all n > n0. } [2]

The question is why we need big-O complexity representation when we already have the
big-Θ notation, which represents the tightly bound running time for any algorithm. Let's
take a small example to understand this.

Consider Linear Search algorithm, in which we traverse an array elements, one by one to
search a given number. [1]

In Worst case, starting from the start position of the array, we find the element or number
we are searching for at the end, that lead to a time complexity of n, where n represents the
number of total elements.

But it can happen that the element that we are searching for is the first element of the
array, in that case the time complexity will be 1.
Now in this case, saying that the big-Θ or tight bound time complexity for Linear search is
Θ(n).It means that the time required will always be related to n, as this is the right way to
represent the average time complexity, but when we use the big-O notation, we mean to
say that the time complexity is O(n), which means that the time complexity will never
exceed n, defining the upper bound, hence saying that it can be less than or equal to n,
which is the correct representation.[1]

This is the reason, most of the time you will see Big-O notation being used to represent the
time complexity of any algorithm, because it makes more sense.

Ω Notation

Ω notation express as the lower bound of an algorithm.

f(n)=  (g(n)) implies:  (g(n)) = { f(n) : there exists positive constants c>0 and n0 such that
f(n) ≥ g(n) for all n > n0. } [2]

θ Notation

θ notation express as both the lower bound and the upper bound or tighter bound of an
algorithm.

f(n)=  (g(n)) implies:  (g(n)) = { f(n) : there exists positive constants c1>0, c2>0 and n0 such
that c1.g(n) ≤ f(n) ≤ c2.g(n) for all n > n0. } [2]

OR, if & only if f(n)=O(g(n)) and f(n)=  (g(n)) for all n > n0

For example, if time complexity for some algorithm is represented by the expression 10n2 +
2n, and we use the Big-Θ notation to represent this, then the time complexity would be
Θ(n2), ignoring the constant coefficient and removing the insignificant part, which is 2n.
Properties of Asymptotic Notations[2]:

1. General Properties :
If f(n) is O(g(n)) then a*f(n) is also O(g(n)) ; where a is a constant.(1)
Example: f(n) = n²+5 is O(n²)
then 7*f(n) = 7(n²+5)
= 7n²+35 is also O(n²)
This property also property satisfies for both Θ and Ω notation.

If f(n) is Θ(g(n)) then a*f(n) is also Θ(g(n)) ; where a is a constant.

If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)) ; where a is a constant.
2. Reflexive Properties :
If f(n) is given then f(n) is O(f(n)).
Example: f(n) = n² ; O(n²) i.e O(f(n))
This property also property satisfies for both Θ and Ω notation.

If f(n) is given then f(n) is Θ(f(n)).

If f(n) is given then f(n) is Ω (f(n)).
3. Transitive Properties :
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n)) .
 Example: if f(n) = n , g(n) = n² and h(n)=n³
n is O(n²) and n² is O(n³)
then n is O(n³)
This property also satisfies for both Θ and Ω notation.

If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n)) .

If f(n) is Ω (g(n)) and g(n) is Ω (h(n)) then f(n) = Ω (h(n))
4. Symmetric Properties :
If f(n) is Θ(g(n)) then g(n) is Θ(f(n)) .
Example: f(n) = n² and g(n) = n²
then f(n) = Θ(n²) and g(n) = Θ(n²)
This property only satisfies for Θ notation.
5. Transpose Symmetric Properties :
If f(n) is O(g(n)) then g(n) is Ω (f(n)).
Example: f(n) = n , g(n) = n²
then n is O(n²) and n² is Ω (n)
This property only satisfies for O and Ω notations.
6. Some More Properties :
1. If f(n) = O(g(n)) and f(n) = Ω(g(n)) then f(n) = Θ(g(n))
2. If f(n) = O(g(n)) and d(n)=O(e(n))
then f(n) + d(n) = O( max( g(n), e(n) ))
Example: f(n) = n i.e O(n)
d(n) = n² i.e O(n²)
then f(n) + d(n) = n + n² i.e O(n²)
3. If f(n)=O(g(n)) and d(n)=O(e(n))
then f(n) * d(n) = O( g(n) * e(n) )
Example: f(n) = n i.e O(n)
d(n) = n² i.e O(n²)
then f(n) * d(n) = n * n² = n³ i.e O(n³)

Examples on Big-O notation(Upper bound/Worst case)

1) Find upper bound for f(n)=2n+2

Solution:

2n+2<=4n, for all n>=1

 2n+2=O(n) with c=4 and n0 =1

2) Find upper bound for f(n)=2n2+1

Solution:

2n2+1<=3n2, for all n>=1

So 2n2+1=O(n2) with c=3 and n0 =1

3) Find upper bound for f(n)=5n4+4n+1

Solution:

5n4+4n+1 <=7n4, for all n>=2

So 5n4+4n+1 =O(n4) with c=7 and n0 =2

Examples on Big- Ω notation (Lower bound/ Best case)

1) Find lower bound for f(n)=2n+2

Solution:

2n<=2n+2, for all n>=1

So 2n+2= Ω(n) with c=2 and n0 =1

2) Find lower bound for f(n)=2n2+1

Solution:

n2<=2n2+1, for all n>=1

So 2n2+1= Ω(n2) with c=1 and n0 =1

3) Find lower bound for f(n)=5n4+4n+1

Solution:

4n4 <=5n4+4n+1, for all n>=1

 So 5n4+4n+1 = Ω(n4) with c=4 and n0 =1

Examples on Big- θ Notation (Tight bound/ Average case)

1) Find tight bound for f(n)=2n+2

Solution:

2n<=2n+2<=4n, for all n>=1

So 2n+2= θ(n) with c1 =2, c2 =4 and n0 =1

2) Find lower bound for f(n)=2n2+1

Solution:

n2<=2n2+1<=3n2, for all n>=1

So 2n2+1= θ(n2) with c1 =1, c2 =3 and n0 =1

Time complexity and Space complexity

 Time complexity:

– The amount of time required by an algorithm to be executed is called its time

complexity

Space Complexity:

– The amount of space required by an algorithm to be executed is called its space

complexity

Analysis of recursive algorithms through recurrence

Recurrence relations:

• Refer as an equation that recursively defines a sequence where the next term
is a function of the previous terms
• Can easily describe the runtime of recursive algorithms.
 The base case(termination condition) is reached when n == 0. The method performs
one comparison. Thus, the number of operations when n == 0, T(0), is some
constant c.

When n !=0, the method calls itself,

using ONE recursive call, with a parameter n – 1.

Therefore the recurrence relation is:

Recursive Case: T(n)=T(n-1),for n>0

Base Case: T(n)=c , for n=0 (Here T(n) is running time and n is input size)

Recurrence relation for factorial is T(n)=T(n-1) , for n>0

T(n)=c, for n=0

Solving Recurrence Relation

I. Substitution Method
II. Iterative Method
III. Recurrence Tree Method
IV. Master’s Method

Solving Recurrence Relations using Substitution Method

I. T(n)=T(n-1)+1, for n>0

T(n)=1, for n=0

Solution:

T(n)=T(n-1)+1 ...........................1)

find T(n-1) and put value in equation 1)

T(n-1)=T(n-2)+1 ..........................2)

T(n-2)=T(n-3)+1 .........................3)

put the value of equation 2) and 3) in 1)

T(n)=T(n-3)+3

continue for k times .now equation look like,

T(n)=T(n-k)+k

to reach base case ,n-k=0 so k=n

T(n)=T(n-n)+n

T(n)=1+n

so ,T(n)=O(n)

II. T(n)=T(n-1)+n, for n>1

T(n)=1, for n=1

Solution:

T(n)=T(n-1)+n ......................1)

T(n-1)=T(n-2)+(n-1)

T(n-2)=T(n-3)+(n-2)

Put the value in equation 1)

T(n)=T(n-2)+(n-1)+n

T(n)=T(n-3)+(n-2)+(n-1)+n .......................2)
 continue for k times .now equation look like,

T(n)=T(n-(k+1))+(n-k)+.......(n-2)+(n-1)+n .....................3)

To reach base case ,n-(k+1)=1 so k=n-2

Put the value in equation 2)

T(n)=T(n-(n-2+1))+(n-(n-2))+.......(n-2)+(n-1)+n

T(n)=T(1)+2+.......(n-2)+(n-1)+n

T(n)=1+2+.......(n-2)+(n-1)+n

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

So T(n)=O(n2)

References :

[1] https://www.studytonight.com/data-structures/aysmptotic-notations
[2]https://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/
 Chapter: 1 Introduction

I. Recurrence tree Method

In some of the cases substitute method is hard to apply and therefore require having
easy way to guess the solution of recurrence equation. Recurrence Tree method is a
graphical tree based approach to solve recurrence problems. It is basically divide and
concur based approach where the problem is sub divided in to small sub problems and
then at each level of Tree the cost is sum up which is known as pre-level cost. At last all
pre-level cost is summed up to have final cost.

It provide good guess for the solution which can be then verified with the help of
substitution method. Let’s understand the process by taking examples.

How to Derive the Recurrence Tree from given Recurrence Equation?

Steps:
Step 1: Identify the root
Step 2: Identify the sub problems
Step 3: Further divide the sub problems and each level.
Step 4: Compute pre-level cost at each level
Step 5: sum up all pre-level cost to have final complexity.

• Example: T (n) = 2T (n/2)+ n2

In given problem,

• The root will be - n2

• Now the problem will be divided in to sub problems.
• So 2T(n/2)= T(n/2)+T(n/2)
Example: for given T (n) = 3T (⌊n/4⌋) + Θ(n2),let’s find out the best guess. Let’s begin
with finding an upper bound for the solution. Because floors and ceilings are usually
insubstantial in solving recurrences (here's an example of sloppiness that we can
tolerate), we create a recursion tree for the recurrence T (n) = 3T(n/4) + cn2, having
written out the implied constant coefficient c > 0.

In above example T(n) is sub divided into three parts each of T(n/4) and then each sub
problem will be divided into further sub problem as shown in below figure. We continue
expanding each node in the tree by breaking it into its constituent parts as determined
by the recurrence.

Fig:1 Recurrence tree for T (n) = 3T (⌊n/4⌋) + Θ(n2)

Characteristics of Recurrence tree can be given below,

➢ Tree has height of log4n.

➢ At last level number of sub problems will be O(nlog43)
➢ Because sub problem sizes decrease as we get further from the root, we
eventually must reach a boundary condition. How far from the root do we reach
one? The sub problem size for a node at depth i is n/4i. Thus, the subproblem
size hits n = 1 when n/4i = 1 or, equivalently, when i = log4 n. Thus, the tree has
log 4n + 1 levels (0, 1, 2,..., log4 n).
➢ Next we determine the cost at each level of the tree. Each level has three times
more nodes than the level above, and so the number of nodes at depth i is 3i.
Because subproblem sizes reduce by a factor of 4 for each level we go down
from the root, each node at depth i, for i = 0, 1, 2,..., log4 n - 1, has a cost of
c(n/4i)2. Multiplying, we see that the total cost over all nodes at depth i, for i = 0,
1, 2,..., log4 n - 1, is 3i c(n/4i)2 = (3/16)i cn2. The last level, at depth log4 n, has
nodes, each contributing cost T (1), for a total cost of O(nlog43).
➢ Now we add up the costs over all levels to determine the cost for the entire tree:

Let’s take advantage of small amounts of sloppiness and use an infinite decreasing
geometric series as an upper bound.
Thus, we have derived a guess of T (n) = O(n2).Now let’s verify it with substitution
method.

Which holds for any d>=(16/13)C.

II. Master’s Theorem

It’s a cook book method for solving the recurrence of the given form,

T(n)=a(n/b) +f(n)

Where a>=1 and b >1 and f(n) is asymptotic positive function of n.here the problem is
divided in to a sub problems with size of (n/b).After solve the sub problems the cost is
added to have final cost. So final f(n)=D(n)+C(n).
Master’s Theorem.

For given recurrence T(n)=a(n/b) +f(n), there are following possible cases.

1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)
3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))

• Master method is mainly derived from recurrence tree method. If we draw

recurrence tree of T(n) = aT(n/b) + f(n), we can see that the work done at root is
f(n) and work done at all leaves is Θ(nc) where c is Logba. And the height of
recurrence tree is Logbn.

• In recurrence tree method, we calculate total work done. If the work done at
leaves is polynomially more, then leaves are the dominant part, and our result
becomes the work done at leaves (Case 1).

• If work done at leaves and root(f(n)) is asymptotically same, then our result
becomes height multiplied by work done at any level (Case 2).
• If work done at root(f(n)) is asymptotically more, then our result becomes work
done at root (Case 3).

Let’s discuss each case by giving example.

Case 1:
Lets take. T (n) = 9T(n/3) + n.
In given recurrence, we have find a = 9, b = 3, f (n) = n.so Θ(nLogba)=Θ(n2) .Since f(n)=n
, where c= 1.
we can apply case 1 of the master theorem and conclude that the solution is T (n)
= Θ(n2).

Case 2:

Lets take. T (n) = T (2n/3) + 1.

In given recurrence, we have find a = 1, b = 3/2, f (n) = 1. So Θ(nLog ba)=Θ(nlog 3/2 1) =n0
=1. Since f(n)=1.

we can apply case 2 of the master theorem and conclude that the solution is T (n)
= Θ(log n).

Case 3:
Let’s take T(n) = 3T(n/4) + n lg n.
we have a = 3, b = 4, f (n) = n lg n, and Θ(nLogba)= Θ(n0.793) . Since f(n)= Θ(n0.793+c)
Where c=0.217

so case 3 can be apply so T(n)= Θ(f(n)).For sufficiently large n, a f(n/b) = 3(n/4)

lg(n/4) ≤ (3/4)n lg n = cf (n) for c = 3/4. Consequently, by case 3, the solution to the
recurrence is T(n) = Θ(n lg n).

Case Where Master method can not apply:

Let’s take T(n/2)=2T(n/2)+n lg n

Even though it has the proper form: a=2,b=2,f(n)=n lg n, and n logba =n,Now f(n)=n lg n
which is greater than nlogba =n. This is actually not a polynomially larger. That is the
ration is (n lg n)/n=lg n is asymptotically less that nc for any c
So actually this is not case 2 or case 3 but this case fall between case 2 and case
3.So master method can not apply here.