Analysis and Design of Algorithms

(UNIT-I)
Prepared by:
Neeraj Sharma
What are Data Structures?
• Data Structure can be defined as the grouping scheme of data elements which will
provides an efficient way of storing, organising, and accessing data elements.

• Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data
Structures are widely used in almost every aspect of Computer Science i.e. Operating
System, Compiler Design, Artificial intelligence, Graphics and many more.

• Data Structures are the main part of many computer science algorithms as they enable the
programmers to handle the data in an efficient way.

• It plays a vital role in enhancing the performance of a software or a program as the main
function of the software is to store and retrieve the user's data as fast as possible.
Basic Terminology
• Data structures are the building blocks of any program or the software.
• Choosing the appropriate data structure for a program is the most difficult task for a
programmer. Following terminology is used as far as data structures are concerned.
– Data: Data can be defined as an elementary value or the collection of values, for
example, student's name and its id are the data about the student.
– Group Items: Data items which have subordinate data items are called Group item, for
example, name of a student can have first name and the last name.
– Record: Record can be defined as the collection of various data items, for example, if
we talk about the student entity, then its name, address, course and marks can be
grouped together to form the record for the student.
– File: A File is a collection of various records of one type of entity, for example, if there
are 60 employees in the class, then there will be 20 records in the related file where
each record contains the data about each employee.
– Attribute and Entity: An entity represents the class of certain objects. it contains
various attributes. Each attribute represents the particular property of that entity.
– Field: Field is a single elementary unit of information representing the attribute of an
entity.
Types of Data Structures
Linear Data Structures
• A data structure is called linear if all of its elements are arranged in the linear order. In
linear data structures, the elements are stored in non-hierarchical way where each element
has the successors and predecessors except the first and last element.

Types of Linear Data Structures are given below:

– Arrays: An array is a collection of similar type of data items and each data item is
called an element of the array. The data type of the element may be any valid data type
like char, int, float or double. The elements of array share the same variable name but
each one carries a different index number known as subscript. The array can be one
dimensional, two dimensional or multidimensional.
The individual elements of the array age are:
age[0], age[1], age[2], age[3],......... age[98], age[99].
Linear Data Structures
• Linked List: Linked list is a linear data structure which is used to maintain a list in the
memory. It can be seen as the collection of nodes stored at non-contiguous memory
locations. Each node of the list contains a pointer to its adjacent node.

• Stack: Stack is a linear list in which insertion and deletions are allowed only at one end,
called top.

• A stack is an abstract data type (ADT), can be implemented in most of the programming
languages. It is named as stack because it behaves like a real-world stack, for example: -
piles of plates or deck of cards etc.

• Queue: Queue is a linear list in which elements can be inserted only at one end
called rear and deleted only at the other end called front.
It is an abstract data structure, similar to stack. Queue is opened at both end therefore it
follows First-In-First-Out (FIFO) methodology for storing the data items.
Data Structures Operations
• Traversing: Every data structure contains the set of data elements. Traversing the data
structure means visiting each element of the data structure in order to perform some
specific operation like searching or sorting.

Example: If we need to calculate the average of the marks obtained by a student in 6

different subject, we need to traverse the complete array of marks and calculate the total
sum, then we will devide that sum by the number of subjects i.e. 6, in order to find the
average.

• Insertion: Insertion can be defined as the process of adding the elements to the data
structure at any location.
If the size of data structure is n then we can only insert n-1 data elements into it.
Data Structures Operations
• Deletion: The process of removing an element from the data structure is called Deletion.
We can delete an element from the data structure at any random location.
If we try to delete an element from an empty data structure then underflow occurs.

• Searching: The process of finding the location of an element within the data structure is
called Searching. There are two algorithms to perform searching, Linear Search and Binary
Search. We will discuss each one of them later in this tutorial.

• Sorting: The process of arranging the data structure in a specific order is known as Sorting.
There are many algorithms that can be used to perform sorting, for example, insertion sort,
selection sort, bubble sort, etc.

• Merging: When two lists List A and List B of size M and N respectively, of similar type of
elements, clubbed or joined to produce the third list, List C of size (M+N), then this process
is called merging
What is Algorithm?
• A finite set of instruction that specifies a sequence of operation is to be carried out in order
to solve a specific problem or class of problems is called an Algorithm.
Why study Algorithm?
• As the speed of processor increases, performance is frequently said to be less central than
other software quality characteristics (e.g. security, extensibility, reusability etc.).

• However, large problem sizes are commonplace in the area of computational science,
which makes performance a very important factor.

• This is because longer computation time, to name a few mean slower results, less through
research and higher cost of computation (if buying CPU Hours from an external party).

• The study of Algorithm, therefore, gives us a language to express performance as a function

of problem size.
Analysis of Algorithm

• Algorithm analysis is an important part of computational complexity theory, which

provides theoretical estimation for the required resources of an algorithm to solve a specific
computational problem.

• Analysis of algorithms is the determination of the amount of time and space resources
required to execute it.
Why Analysis of Algorithm is important?

• To predict the behaviour of an algorithm without implementing it on a specific computer.

• It is much more convenient to have simple measures for the efficiency of an algorithm than
to implement the algorithm and test the efficiency every time a certain parameter in the
underlying computer system changes.

• It is impossible to predict the exact behaviour of an algorithm. There are too many
influencing factors.

• The analysis is thus only an approximation; it is not perfect.

• More importantly, by analyzing different algorithms, we can compare them to determine

the best one for our purpose.
Types of Algorithm Analysis

• Best case: Define the input for which algorithm takes less time or minimum time. In the
best case calculate the lower bound of an algorithm. Example: In the linear search when
search data is present at the first location of large data then the best case occurs.

• Worst Case: Define the input for which algorithm takes a long time or maximum time. In
the worst calculate the upper bound of an algorithm. Example: In the linear search when
search data is not present at all then the worst case occurs.

• Average case: In the average case take all random inputs and calculate the computation
time for all inputs.

And then we divide it by the total number of inputs.

Average case = all random case time / total no of case

Design of Algorithm

• An algorithm can be defined as a finite set of steps, which has to be followed while
carrying out a particular problem.

• It is nothing but a process of executing actions step by step.

• An algorithm is a distinct computational procedure that takes input as a set of values and
results in the output as a set of values by solving the problem.

• An algorithm unravels the computational problems to output the desired result.

• An algorithm can be described by incorporating a natural language such as English,

Computer language, or a hardware language.
Characteristics of Algorithms
• Input: It should externally supply zero or more quantities.
• Output: It results in at least one quantity.
• Definiteness: Each instruction should be clear and ambiguous.
• Finiteness: An algorithm should terminate after executing a finite number of steps.
• Effectiveness: Every instruction should be fundamental to be carried out, in principle, by a
person using only pen and paper.
• Feasible: It must be feasible enough to produce each instruction.
• Flexibility: It must be flexible enough to carry out desired changes with no efforts.
• Efficient: The term efficiency is measured in terms of time and space required by an
algorithm to implement. Thus, an algorithm must ensure that it takes little time and less
memory space meeting the acceptable limit of development time.
• Independent: An algorithm must be language independent, which means that it should
mainly focus on the input and the procedure required to derive the output instead of
depending upon the language.
Advantages of an Algorithms
• Effective Communication: Since it is written in a natural language like English, it
becomes easy to understand the step-by-step delineation of a solution to any particular
problem.

• Easy Debugging: A well-designed algorithm facilitates easy debugging to detect the

logical errors that occurred inside the program.

• Easy and Efficient Coding: An algorithm is nothing but a blueprint of a program that
helps develop a program.

• Independent of Programming Language: Since it is a language-independent, it can be

easily coded by incorporating any high-level language.
Disadvantages of an Algorithms
• Developing algorithms for complex problems would be time-consuming and difficult to
understand.

• It is a challenging task to understand complex logic through algorithms.

 Pseudocode
• Pseudocode refers to an informal high-level description of the operating principle of a
computer program or other algorithm.
• It uses structural conventions of a standard programming language intended for human
reading rather than the machine reading.
Advantages of Pseudocode
• Since it is similar to a programming language, it can be quickly transformed into the actual
programming language than a flowchart.
• The layman can easily understand it.
• Easily modifiable as compared to the flowcharts.
• Its implementation is beneficial for structured, designed elements.
• It can easily detect an error before transforming it into a code.
Disadvantages of Pseudocode
• Since it does not incorporate any standardized style or format, it can vary from one
company to another.
• Error possibility is higher while transforming into a code.
• It may require a tool for extracting out the Pseudocode and facilitate drawing flowcharts.
• It does not depict the design.
Difference b/w Algorithm and the Pseudocode

• An algorithm is simply a problem-solving process, which is used not only in computer

science to write a program but also in our day to day life. It is nothing but a series of
instructions to solve a problem or get to the problem's solution. It not only helps in
simplifying the problem but also to have a better understanding of it.

• However, Pseudocode is a way of writing an algorithm. Programmers can use informal,

simple language to write pseudocode without following any strict syntax. It encompasses
semi-mathematical statements.
• Problem: Suppose there are 60 students in the class. How will you calculate the
number of absentees in the class?

Pseudo Approach Algorithm Approach

1.Initialize a variable called as Count to 1.Count <- 0, absent <- 0, total <- 60
zero, absent to zero, total to 60
2.REPEAT till all students counted
2.FOR EACH Student PRESENT DO the Count <- Count + 1
following:
Increase the Count by One 3.absent <- total - Count
Print "Number absent is:" , absent
3.ThenSubtract Count from total and
store the result in absent

4.Display the number of absent students

Complexity of Algorithm
• The term algorithm complexity measures how many steps are required by the algorithm to
solve the given problem.
• It evaluates the order of count of operations executed by an algorithm as a function of input
data size.
• To assess the complexity, the order (approximation) of the count of operation is always
considered instead of counting the exact steps.
• O(f) notation represents the complexity of an algorithm, which is also termed as an
Asymptotic notation or "Big O" notation. Here the f corresponds to the function whose size
is the same as that of the input data.
• The complexity of the asymptotic computation O(f) determines in which order the
resources such as CPU time, memory, etc. are consumed by the algorithm that is articulated
as a function of the size of the input data.
• The complexity can be found in any form such as constant, logarithmic, linear, n*log(n),
quadratic, cubic, exponential, etc.
Typical Complexity of an Algorithm
• Constant Complexity:
It imposes a complexity of O(1). It undergoes an execution of a constant number of steps
like 1, 5, 10, etc. for solving a given problem. The count of operations is independent of the
input data size.

• Logarithmic Complexity:
It imposes a complexity of O(log(N)). It undergoes the execution of the order of log(N)
steps. To perform operations on N elements, it often takes the logarithmic base as 2.
For N = 1,000,000, an algorithm that has a complexity of O(log(N)) would undergo 20
steps. Here, the logarithmic base does not hold a necessary consequence for the operation
count order, so it is usually omitted.
Typical Complexity of an Algorithm
• Linear Complexity:
– It imposes a complexity of O(N). It encompasses the same number of steps as that of
the total number of elements to implement an operation on N elements.
For example, if there exist 500 elements, then it will take about 500 steps. Basically, in
linear complexity, the number of elements linearly depends on the number of steps. For
example, the number of steps for N elements can be N/2 or 3*N.

– It also imposes a run time of O(n*log(n)). It undergoes the execution of the order
N*log(N) on N number of elements to solve the given problem.
For a given 1000 elements, the linear complexity will execute 10,000 steps for solving
a given problem.
Typical Complexity of an Algorithm
• Quadratic Complexity: It imposes a complexity of O(n2). For N input data size, it
undergoes the order of N2 count of operations on N number of elements for solving a given
problem. If N = 100, it will endure 10,000 steps. In other words, whenever the order of
operation tends to have a quadratic relation with the input data size, it results in quadratic
complexity. For example, for N number of elements, the steps are found to be in the order
of 3*N2/2.

• Cubic Complexity: It imposes a complexity of O(n3). For N input data size, it executes the
order of N3 steps on N elements to solve a given problem.
For example, if there exist 100 elements, it is going to execute 1,000,000 steps.

• Exponential Complexity: It imposes a complexity of O(2n), O(N!), O(nk), …. For N

elements, it will execute the order of count of operations that is exponentially dependable
on the input data size.
Algorithm Design Techniques

• The following is a list of several popular design approaches:

1. Divide and Conquer Approach: It is a top-down approach. The algorithms which follow
the divide & conquer techniques involve three steps:

 Divide the original problem into a set of subproblems. Divide Part

 Solve every subproblem individually, recursively. conqure part
 Combine the solution of the subproblems (top level) into a solution of the whole
original problem. optional
Algorithm Design Techniques
2. Greedy Technique: Greedy method is used to solve the optimization problem. An
optimization problem is one in which we are given a set of input values, which are required
either to be maximized or minimized (known as objective), i.e. some constraints or
conditions.

 Greedy Algorithm always makes the choice (greedy criteria) looks best at the moment,
to optimize a given objective.
 The greedy algorithm doesn't always guarantee the optimal solution however it
generally produces a solution that is very close in value to the optimal.
Algorithm Design Techniques
3. Dynamic Programming: Dynamic Programming is a bottom-up approach we solve all
possible small problems and then combine them to obtain solutions for bigger problems.
This is particularly helpful when the number of copying subproblems is exponentially
large. Dynamic Programming is frequently related to Optimization Problems.

4. Branch and Bound: In Branch & Bound algorithm a given subproblem, which cannot be
bounded, has to be divided into at least two new restricted subproblems. Branch and Bound
algorithm are methods for global optimization in non-convex problems. Branch and Bound
algorithms can be slow, however in the worst case they require effort that grows
exponentially with problem size, but in some cases we are lucky, and the method coverage
with much less effort.

5. Backtracking Algorithm: Backtracking Algorithm tries each possibility until they find the
right one. It is a depth-first search of the set of possible solution. During the search, if an
alternative doesn't work, then backtrack to the choice point, the place which presented
different alternatives, and tries the next alternative.
Algorithm Design Techniques

6. Randomized Algorithm: A randomized algorithm uses a random number at least once

during the computation make a decision. A randomized algorithm is defined as an
algorithm that is allowed to access a source of independent, unbiased random bits, and it is
then allowed to use these random bits to influence its computation.

Example 1: In Quick Sort, using a random number to choose a pivot.

Example 2: Trying to factor a large number by choosing a random number as possible

divisors.
Asymptotic notation

• The word Asymptotic means approaching a value or curve arbitrarily closely. Asymptotic
notations are used to write fastest and slowest possible running time for an algorithm.
These are also referred to as 'best case' and 'worst case' scenarios respectively.

• In asymptotic notations, we derive the complexity concerning the size of the input.
(Example in terms of n)“

• These notations are important because they give an approximation about the cost of running
the algorithm.

• They give simple characteristics of an algorithm's efficiency.

• They allow the comparisons of the performances of various algorithms.

Asymptotic Notation
• Asymptotic Notation is a way of comparing function that ignores constant factors and small
input sizes. Three notations are used to calculate the running time complexity of an
algorithm:
1. Big-oh notation: Given two functions f(n) and g(n), we say that f(n) is O(g(n)) if there
exist constants c > 0 and n0 >= 0 such that f(n) <= c*g(n) for all n >= n0.

Hence, function g (n) is an upper bound for function f (n), as g (n) grows faster than f (n)
For Example:
1. 3n+2=O(n) as 3n+2≤4n for all n≥2
2. 3n+3=O(n) as 3n+3≤4n for all n≥3
Hence, the complexity of f(n) can be represented as
O (g (n))
Asymptotic Notation
2. Omega () Notation: The function f (n) = Ω (g (n)) [read as "f of n is omega of g of n"] if
and only if there exists positive constant c and n0 such that

F (n) ≥ k* g (n) for all n, n≥ n0

For Example:
f (n) = 8n2+2n-3 ≥ 8n2-3
= 7n2+(n2-3) ≥ 7n2 (g(n))
Thus, k1=7

Hence, the complexity of f (n) can be represented as Ω (g (n))

Asymptotic Notation

3. Theta (θ): The function f (n) = θ (g (n)) [read as "f is the theta of g of n"] if and only if there
exists positive constant k1, k2 and k0 such that

k1 * g (n) ≤ f(n)≤ k2 g(n)for all n, n≥ n0

For Example:
3n+2= θ (n) as 3n+2≥3n and 3n+2≤ 4n, for n
k1=3,k2=4, and n0=2

Hence, the complexity of f (n) can be represented

as θ (g(n)).

The Theta Notation is more precise than both the big-oh and Omega notation. The function
f(n) = θ (g (n)) if g(n) is both an upper and lower bound.
Growth of function
• Resources for an algorithm are usually expressed as a function regarding input. Often this
function is messy and complicated to work. To study Function growth efficiently, we
reduce the function down to the important part.

Let f (n) = an2+bn+c

In this function, the n2 term dominates the function that is when n gets sufficiently large.
Dominate terms are what we are interested in reducing a function, in this; we ignore all
constants and coefficient and look at the highest order term concerning n.
Recurrence Relation
• A recurrence is an equation or inequality that describes a function in terms of its values on
smaller inputs.
• To solve a Recurrence Relation means to obtain a function defined on the natural numbers
that satisfy the recurrence.
For Example, the Worst Case Running Time T(n) of the MERGE SORT Procedures is
described by the recurrence.
T (n) = θ (1) if n=1
2T(n/2) + θ (n) if n>1
There are four methods for solving Recurrence:
– Substitution Method
– Iteration Method
– Recursion Tree Method
– Master Method
Substitution Method:
• The Substitution Method Consists of two main steps:
– Guess the Solution.
– Use the mathematical induction to find the boundary condition and shows that the
guess is correct.
For Example1 Solve the equation by Substitution Method.
T (n) = T(n/2) + n
We have to show that it is asymptotically bound by O (log n).
Solution: For T (n) = O (log n)
Put this in given Recurrence Equation.
T (n) ≤c log+ 1
≤c log+ 1 = c logn-clog2 2+1
≤c logn for c≥1
Thus T (n) =O logn.
Substitution Method:
Example2 Consider the Recurrence
T (n) = 2T(n/2)+ n n>1
Find an Asymptotic bound on T.
Solution:
We guess the solution is O (n (logn)).Thus for constant 'c'.
T (n) ≤c n logn
Put this in given Recurrence Equation.
Now,
T (n) ≤2c(n/2)log(n/2) +n
≤cnlogn-cnlog2+n
=cn logn-n (clog2-1)
≤cn logn for (c≥1)
Thus T (n) = O (n logn).
Iteration Method:

• It means to expand the recurrence and express it as a summation of terms of n and initial
condition.
Example1: Consider the Recurrence
T (n) = 1 if n=1
= 2T (n-1) if n>1
Solution:
T (n) = 2T (n-1)
= 2[2T (n-2)] = 22T (n-2)
= 4[2T (n-3)] = 23T (n-3)
= 8[2T (n-4)]
= 24T (n-4) (Eq.1)
Repeat the procedure for i times
T (n) = 2i T (n-i)
Put n-i=1 or i= n-1 in (Eq.1)
T (n) = 2n-1 T (1)
= 2n-1 .1 {T (1) =1 .....given}
= 2n-1
Recursion Tree Method:

• Recursion Tree Method is a pictorial representation of an iteration method which is in the

form of a tree where at each level nodes are expanded.

• In general, we consider the second term in recurrence as root.

• It is useful when the divide & Conquer algorithm is used.

• It is sometimes difficult to come up with a good guess. In Recursion tree, each root and
child represents the cost of a single subproblem.

• We sum the costs within each of the levels of the tree to obtain a set of pre-level costs and
then sum all pre-level costs to determine the total cost of all levels of the recursion.

• A Recursion Tree is best used to generate a good guess, which can be verified by the
Substitution Method.
Recursion Tree Method:
Example 1
Consider T (n) = 2T(n/2) + n2
We have to obtain the asymptotic bound using recursion tree method.
Solution: The Recursion tree for the above recurrence is
Master Method:
The Master Method is used for solving the following types of recurrence

T (n) = a T(n/b)+ f (n) with a≥1 and b≥1 be constant & f(n) be a function and n/b can be
interpreted as

Let T (n) is defined on non-negative integers by the recurrence.

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

In the function to the analysis of a recursive algorithm, the constants and function take on the
following significance:
Master Method:
• n is the size of the problem.

• a is the number of subproblems in the recursion.

• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially
the same size.)

• f (n) is the sum of the work done outside the recursive calls, which includes the sum of
dividing the problem and the sum of combining the solutions to the subproblems.

• It is not possible always bound the function according to the requirement, so we make three
cases which will tell us what kind of bound we can apply on the function.
Divide and Conquer Introduction

• Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take
a dispute on a huge input, break the input into minor pieces, decide the problem on each of
the small pieces, and then merge the piecewise solutions into a global solution. This
mechanism of solving the problem is called the Divide & Conquer Strategy.

• Divide and Conquer algorithm consists of a dispute using the following three steps.
– Divide the original problem into a set of subproblems.
– Conquer: Solve every subproblem individually, recursively.
– Combine: Put together the solutions of the subproblems to get the solution to the whole
problem.
Divide and Conquer Introduction
Divide and Conquer Introduction

• Generally, we can follow the divide-and-conquer approach in a three-step process.

Examples: The specific computer algorithms are based on the Divide & Conquer approach:

– Binary Search
– Sorting (merge sort, quick sort)
– Tower of Hanoi.
Fundamental Divide and Conquer Strategy
• There are two fundamental of Divide & Conquer Strategy:
– Recurrence Formula
– Stopping Condition

1. Recurrence Formula: It is the formula that we generate from the given technique. After
generation of Formula we apply D&C Strategy, i.e. we break the problem recursively &
solve the broken subproblems.

2. Stopping Condition: When we break the problem using Divide & Conquer Strategy, then
we need to know that for how much time, we need to apply divide & Conquer. So the
condition where the need to stop our recursion steps of D&C is called as Stopping
Condition.
Application of Divide and Conquer Approach

• Following algorithms are based on the concept of the Divide and Conquer Technique:

• Binary Search: The binary search algorithm is a searching algorithm, which is also called
a half-interval search or logarithmic search. It works by comparing the target value with the
middle element existing in a sorted array. After making the comparison, if the value differs,
then the half that cannot contain the target will eventually eliminate, followed by
continuing the search on the other half. We will again consider the middle element and
compare it with the target value. The process keeps on repeating until the target value is
met. If we found the other half to be empty after ending the search, then it can be concluded
that the target is not present in the array.

• Quicksort: It is the most efficient sorting algorithm, which is also known as partition-
exchange sort. It starts by selecting a pivot value from an array followed by dividing the
rest of the array elements into two sub-arrays. The partition is made by comparing each of
the elements with the pivot value. It compares whether the element holds a greater value or
lesser value than the pivot and then sort the arrays recursively.
Application of Divide and Conquer Approach
• Merge Sort: It is a sorting algorithm that sorts an array by making comparisons. It starts by
dividing an array into sub-array and then recursively sorts each of them. After the sorting is
done, it merges them back.
• Closest Pair of Points: It is a problem of computational geometry. This algorithm
emphasizes finding out the closest pair of points in a metric space, given n points, such that
the distance between the pair of points should be minimal.
• Strassen's Algorithm: It is an algorithm for matrix multiplication, which is named after
Volker Strassen. It has proven to be much faster than the traditional algorithm when works
on large matrices.
• Cooley-Tukey Fast Fourier Transform (FFT) algorithm: The Fast Fourier Transform
algorithm is named after J. W. Cooley and John Turkey. It follows the Divide and Conquer
Approach and imposes a complexity of O(nlogn).
• Karatsuba algorithm for fast multiplication: It is one of the fastest multiplication
algorithms of the traditional time, invented by Anatoly Karatsuba in late 1960 and got
published in 1962. It multiplies two n-digit numbers in such a way by reducing it to at most
single-digit.
Advantages of Divide and Conquer

• Divide and Conquer tend to successfully solve one of the biggest problems, such as the
Tower of Hanoi, a mathematical puzzle. It is challenging to solve complicated problems for
which you have no basic idea, but with the help of the divide and conquer approach, it has
lessened the effort as it works on dividing the main problem into two halves and then solve
them recursively. This algorithm is much faster than other algorithms.

• It efficiently uses cache memory without occupying much space because it solves simple
subproblems within the cache memory instead of accessing the slower main memory.

• It is more proficient than that of its counterpart Brute Force technique.

• Since these algorithms inhibit parallelism, it does not involve any modification and is
handled by systems incorporating parallel processing.
Disadvantages of Divide and Conquer

• Since most of its algorithms are designed by incorporating recursion, so it necessitates high
memory management.

• An explicit stack may overuse the space.

• It may even crash the system if the recursion is performed rigorously greater than the stack
present in the CPU.
DIVIDE AND CONQUER: GENERAL METHOD

1. Algorithm D And C(P)

2. {
3. if small(P) then return S(P);
4. else
5. {
6. divide P into smaller instances
7. P1, P2… Pk, k>=1;
8. Apply D And C to each of these sub problems;
9. return combine (D And C(P1), D And C(P2),…….,D And C(Pk));
10. }
11. }
Binary Search Algo

• def binary_search_recursive(arr, target, left, right):

• if left <= right:
• mid = (left + right) / 2
• if arr[mid] == target:
• return mid # Target found, return its index
• elif arr[mid] < target:
• return binary_search_recursive(arr, target, mid + 1, right)
• else:
• return binary_search_recursive(arr, target, left, mid - 1)
• return -1 # Target not found
Merge Sort

• Merge sort is yet another sorting algorithm that falls under the category of Divide and
Conquer technique. It is one of the best sorting techniques that successfully build a
recursive algorithm.
• The Merge-Sort function keeps on splitting an array into two halves until a condition is met
where we try to perform Merge-Sort on a subarray of size 1, i.e., p == r.
• And then, it combines the individually sorted sub arrays into larger arrays until the whole
array is merged.

ALGORITHM-MERGE SORT
1. if p <= r
1. Then q → (p+ r)/2
2. MERGE-SORT (A, p, q)
3. MERGE-SORT (A, q+1,r)
4. MERGE (A, p, q, r)
Merge Sort
Merge Sort
Merge Sort

• MERGE_SORT(arr, beg, end) while (i < n1 && j < n2)

{
– if beg <= end
if(LeftArray[i] <= RightArray[j])
– set mid = (beg + end)/2 {
– MERGE_SORT(arr, beg, mid) a[k] = LeftArray[i];
– MERGE_SORT(arr, mid + 1, end) i++; }
– MERGE (arr, beg, mid, end) else
{
a[k] = RightArray[j];
void merge(int a[], int beg, int mid, int end)
j++; }
{
k++; }
int i, j, k;
while (i<n1)
int n1 = mid - beg + 1;
{
int n2 = end - mid;
a[k] = LeftArray[i];
int LeftArray[n1], RightArray[n2];
i++;
for (int i = 0; i < n1; i++)
k++; }
LeftArray[i] = a[beg + i];
while (j<n2)
for (int j = 0; j < n2; j++)
{
RightArray[j] = a[mid + 1 + j];
a[k] = RightArray[j];
i = 0; j = 0; k = beg;
j++;
k++; }}
Quick Sort
• It is an algorithm of Divide & Conquer type.

Divide: Rearrange the elements and split arrays into two sub-arrays and an element in
between search that each element in left sub array is less than or equal to the average
element and each element in the right sub- array is larger than the middle element.
Conquer: Recursively, sort two sub arrays.
Combine: Combine the already sorted array. (optional)
 Quick Sort Algorithm

void quickSort(arr, low, high) Partition algorithm rearranges the sub arrays in a place.
{ PARTITION (array A, int m, int n)
if (low < high) 1 x ← A[m]
{ 2o←m
pi = partition(arr, low, high); 3 for p ← m + 1 to n
quickSort(arr, low, pi - 1); 4 do if (A[p] < x)
quickSort(arr, pi + 1, high); 5 then o ← o + 1
} 6 swap A[o] with A[p]
7 swap A[m] with A[o]
}
8 return o
Strassen’s Matrix Multiplication Algorithm

• Strassen’s Matrix multiplication can be performed only on square matrices where n is

a power of 2. Order of both of the matrices are n × n.

• Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −

Strassen’s Matrix Multiplication Algorithm
Using Strassen’s Algorithm compute the following −
• M1:=(A+C)×(E+F)
• M2:=(B+D)×(G+H)
• M3:=(A−D)×(E+H)
• M4:=A×(F−H)
• M5:=(C+D)×(E)
• M6:=(A+B)×(H)
• M7:=D×(G−E)
Then
• I:=M2+M3−M6−M7
• J:=M4+M6
• K:=M5+M7
• L:=M1−M3−M4−M5
 More on Performance Analysis
Performance Analysis: An algorithm is said to be efficient and fast if it take less
time to execute and consumes less memory space at run time is called Performance
Analysis.

1. SPACE COMPLEXITY:
The space complexity of an algorithm is the amount of Memory Space
required by an algorithm during course of execution is called space complexity .There
are three types of space
a) Instruction space :executable program
b) Data space: Required to store all the constant and variable data space.
c) Environment: It is required to store environment information needed to resume
the suspended space.

2. TIME COMPLEXITY:
The time complexity of an algorithm is the total amount of time required by an
algorithm to complete its execution.
 Space complexity

Now there are two types of space complexity

a) Constant space complexity

b) Linear(variable)space complexity
1.Constant space complexity: A fixed amount of space for all
the input values.

Example : int square(int a)

{
return a*a;
}
Here algorithm requires fixed amount of space for all the
input values.
2.Linear space complexity: The space needed for algorithm is based
on size.
 Size of the variable ‘n’ = 1 word
 Array of a values = n word
 Loop variable = 1 word
 Sum variable = 1 word
Example:
int sum(int A[],int n)
{ n
int sum=0,i; 1
for (i=0;i<n;i++) 1
sum=sum+A[i]; 1
Return sum;
} Ans : 1+n+1+1 = n+3 words
Examples:

1.Algorithm sum(a,b,c)
{
a=10; a-1
b=20; b-1
c=a+b; c-1
}
s(p)=c+sp
3+0=3
0(n)=3
2. algorithm sum(a,n)
{
total-=0; -1
Fori=1 to n do -1,1
Total=total+a[i] --n
Return total
}
 Space
Complexity

Algorithm-1 Algorithm-2 Algorithm-3:recursive procedure

ADA
1.Constant time complexity : If a program required fixed amount
of time for all input values is called Constant time complexity .

Example : int sum(int a , int b)

{
return a+b;
}
2.Linear time complexity: If the input values are increased then the
time complexity will changes.
 comments = 0 step
 Assignment statement= 1 step
 condition statement= 1 step
 loop condition for n times = n+1 steps
 body of the loop = n steps
Example : int sum(int A[],int n)
{
int sum=0,i;
for (i=0;i<n;i++)
sum=sum+A[i];
return sum;}

cost repetation total

1 1 1
1+1+1 1+(n+1)+n 2n+2
2 n 2n
1 1 1
4n+4
ADA
 TIME COMPLEXITY

The time T(p) taken by a program P is the sum of the compile time
and the run time(execution time)
Statement S/e Frequency Total

1. Algorithm Sum(a, n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. for i = 1 to n do 1 n+1 n+1
5. s=s+a[i]; 2 n 2n
6. return s; 1 1 1
7. } 0 - 0

Total 3n+3
 KINDS OF ANALYSIS

1.Worst-case: (usually)
• T(n) = maximum time of algorithm on any input of size n.

2.Average-case: (sometimes)
• T(n) = expected time of algorithm over all inputs of size n.
• Need assumption of statistical distribution of inputs.

3.Best-case:
• T(n) = minimum time of algorithm on any input of size n.

COMPLEXITY:
Complexity refers to the rate at which the storage time grows as a function of the
problem size
 Analysis of an Algorithm
 The goal of analysis of an algorithm is to compare algorithm in running
time and also Memory management.
 Running time of an algorithm depends on how long it takes a
computer to run the lines of code of the algorithm.

Running time of an algorithm depends on

1.Speed of computer
2.Programming language
3.Compiler and translator

Examples: binary search, linear search

 ASYMPTOTIC ANALYSIS

 Expressing the complexity in term of its relationship to know function.

This type analysis is called asymptotic analysis.

 The main idea of Asymptotic analysis is to have a measure of efficiency

of an algorithm , that doesn’t depends on:

1.Machine constants.
2.Doesn’t require algorithm to be implemented.
3.Time taken by program to be prepare.
 ASYMPTOTIC NOTATION

ASYMPTOTIC NOTATION: The mathematical way of representing the Time

complexity.
The notation we use to describe the asymptotic running time of an algorithm are
defined in terms of functions whose domains are the set of natural numbers.

Definition : It is the way to describe the behavior of functions in the limit or

without bounds.
Asymptotic growth: The rate at which the function grows…
“growth rate” is the complexity of the function or the amount of resource it takes
up to compute.

Growth rate Time +memory

 Classification of growth
1. Growing with the same rate.
2. Growing with the slower rate.
3. Growing with the faster rate.
They are 3 asymptotic notations are mostly used to represent
time complexity of algorithm.

1. Big oh (O)notation
2. Big omega (Ω) notation
3. Theta(Θ) notation
4. Little oh (o) notation
5. Little omega(ω) notation
1.Big oh (O) notation:
Asymptotic “less than”(slower rate). This notation mainly represent upper bound
of algorithm run time. Big oh (O)notation is useful to calculate maximum amount of time of
execution.

By using Big-oh notation we have to calculate worst case time complexity.

Formula: f(n)<=c g(n) n>=n0, c>0 ,n0 >=1
Definition: Let f(n) ,g(n) be two non negative (positive) function
now the f(n)=O(g(n)) if there exist two positive constant c,n0 such that
f(n)<= c.g(n) for all value of n>0 & c>0
 Big Oh-notation

 For a given function g(n), we denote by O(g(n)) the set of functions

 f (n) : thereexist positiveconstants c and n0 s.t.

O( g (n))   
 0  f ( n )  cg ( n ) for all n  n 0 

 We use O-notation to give an asymptotic upper bound of a function, to

within a constant factor.
 f(n) = O(g(n)) means that there existes some constant c s.t. f(n) is always
<= c.g(n) for large enough n.
 Examples
Example: f(n)=3n+2 & g(n)= n
Formula: f(n)<=c g(n) n>=n0 , c>0 ,n0 >=1
f(n)=3n+2 & g(n)=n
Now 3n+2<=c.n
3n+2<=4.n
Put the value of n = 1
5<=4 false
N=2 8<=8 true now n0>2 For all value of n>2 & c=4
now f(n)<= c.g(n)
3n+2<=4n for all value of n>=2

Above condition is satisfied this notation takes maximum amount of time to execute. So that it is
called worst case complexity.
 Ω-Omega notation
Ω-Omega notation: Asymptotic “greater than” (faster rate).

It represent Lower bound of algorithm run time. By using Big Omega notation we can
calculate minimum amount of time. We can say that it is best case time complexity.

Formula: f(n)>=c.g(n) n>=n0 , c>0 ,n0 >=1

where c is constant, n is function

 Lower bound
 Best case
 Ω-Omega notation

 For a given function g(n), we denote by Ω(g(n)) the set of functions

 f (n) : there exist positive constants c and n0 s.t.

( g (n))   
 0  cg ( n )  f ( n ) for all n  n0 
 We use Ω-notation to give an asymptotic lower bound on a function, to within a
constant factor.
 f(n) = Ω(g(n)) means that there exists some constant c s.t. f(n) is always >= c.g(n)
for large enough n.
Examples
Example : f(n)=3n +2

Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0 >=1

f(n)=3n+2
3n+2>=1*n, c=1 put the value of n=1
n=1 5>=1 true n0>=1 for all value of n
It means that f(n) = Ω g(n).
 -Theta notation
Theta (Θ) notation : Asymptotic “Equality”(same rate).
 It represent average bond of algorithm running time.
 By using theta notation we can calculate average amount of time.
 So it called average case time complexity of algorithm.

Formula : c1 g(n)<=f(n)<=c2 g(n)

where c is constant, n is function

 Average bound
 Θ-Theta notation
 For a given function g(n), we denote by ( g (n)) the set of functions

 f (n) : there exist positive constants c1 , c2 , and n0 s.t.

( g (n))   
 0  c1 g ( n )  f ( n )  c2 g ( n ) for all n  n0 
 A function f(n) belongs to the set ( g (n)) if there exist positive
constants c1 and c2 such that it can be “sand- wiched” between c1.g(n)
and c2.g(n) or sufficienly large n.
 f (n)  ( g (n)) means that there exists some constant c1 and c2
such that c1 g (n)  f (n)  c2 g (n) for large enough n.
 Examples
Example : f(n)=3n+2
Formula : c1 g(n)<=f(n)<=c2 g(n)
f(n)=2n+3
1*n<=3n+2<=4*n
now put the value of n=1 we get 1<=5<=4 false
n=2 we get 2<=8<=8 true
n=3 we get 3<=11<=12 true
Now all value of n>=2 it is true above condition is satisfied.
Little oh notation

• Little o notation is used to describe an upper bound

that cannot be tight. In other words, loose upper
bound of f(n).
Slower growth rate
f(n) grows slower than g(n)
• When we say that a function f(n) is o(g(n)), we are essentially stating
that f(n) grows slower than g(n) as n approaches infinity. In simpler
terms, if f(n) = o(g(n)), it means that g(n) grows faster than f(n).
Little omega(ω) notation
• Another asymptotic notation is little omega notation. it is denoted
by (ω).
• Little omega (ω) notation is used to describe a loose lower bound of
f(n).
• Faster growth rate
• F(n) grows faster than g(n)
• Formally stated as f(n)=ωg(n)
 Example of Asymptotic notation

Problem:-
Find upper bond ,lower bond & tight bond range for
functions: f(n)= 2n+5
Solution:-
Let us given that f(n)= 2n+5 , now g(n)= n
lower bond=2n, upper bond =3n, tight bond=2n
For Big –oh notation(O):- according to definition
f(n)<=cg(n) for Big oh we use upper bond so
f(n)=2n+5, g(n)=n and c=3 according to definition
2n+5<=3n
Put n=1 7<=3 false Put n=2 9<=6 false Put n=3 14<=9 false Put n=4 13<=12
false Put n=5 15<=15 true
now for all value of n>=5 above condition is satisfied. C=3 n>=5
2. Big - omega notation :- f(n)>=c.g(n) we know that this
Notation is lower bond notation so c=2
Let f(n)=2n+5 & g(n)=2.n
Now 2n+5>=c.g(n);
2n+5>=2n put n=1
We get 7>=2 true for all value of n>=1,c=2 condition is satisfied.
3. Theta notation :- according to definition
c1.g(n)<=f(n)<=c2.g
Thank You