4/1/25, 12:09 PM Evernote

UNIT 4. Algorithm

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,
Divide
and Conquer: General Method, Binary Search, Finding Maximum and Minimum,
Merge Sort.
General Method, Multistage Graphs, All-Pair shortest paths, Optimal binary search
trees.
General Method, 8-Queens problem, Hamiltonian problem.
Connected Components, Spanning Trees, Biconnected components, Introduction to
NP Hard and NP-Completeness.

The word Algorithm means ” A set of finite rules or instructions to be followed in calculations
or other problem-solving operations

its is step by step procedure to solve the computational problems

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 1/9
4/1/25, 12:09 PM Evernote

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 2/9
4/1/25, 12:09 PM Evernote

Example:
Let take f(n)=3n+2 and g(n)=n.

We have to prove f(n) ∈O(g(n)).

By the definition, f(n)≤c g(n) 3n+2≤ c * n where c>0, n0≥1.

We can substitute any value for c. The best option is, When c=4, 3n+2≤ 4 * n. Most
of the cases, 4*n is greater than 3n+2.

Where n≥2. Reason for taking n≥2: If n=1, 3(1)+2 ≤ 4(1)=> 5≤4=> Becomes False.
If n=2, 3(2)+2 ≤ 4(2)=> 8≤8=> Becomes True.
If n=3, 3(3)+2 ≤ 4(3)=> 11≤12=> Becomes True. If n=4, 3(4)+2 ≤ 4(4)=> 14≤16=>
Becomes True. And so on.
https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 3/9
4/1/25, 12:09 PM Evernote

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 4/9
4/1/25, 12:09 PM Evernote

NOTE : The method of taking an input and running through the steps of the
algorithm is sometimes called dry run
. Such a dry run will help us to:
1. Identify any incorrect steps in the algorithm
2. Figure out missing details or specifics in the algorithm

Syntax is the set of rules or grammar that governs the formulation of the statements
in the language, such as spellings, order of words, punctuation, etc.

Divide and Conquer Algorithm Definition:

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 5/9
4/1/25, 12:09 PM Evernote

Divide and Conquer Algorithm involves breaking a larger problem into smaller
subproblems, solving them independently, and then combining their solutions to
solve the original problem. The basic idea is to recursively divide the problem into
smaller subproblems until they become simple enough to be solved directly. Once
the solutions to the subproblems are obtained, they are then combined to produce
the overall solution.

Applications of Divide and Conquer Algorithm:

The following are some standard algorithms that follow Divide and Conquer algorithm:

• Quicksort is a sorting algorithm that picks a pivot element and rearranges the
array elements so that all elements smaller than the picked pivot element move to
the left side of the pivot, and all greater elements move to the right side. Finally,
the algorithm recursively sorts the subarrays on the left and right of the pivot
element.
• Merge Sort is also a sorting algorithm. The algorithm divides the array into two
halves, recursively sorts them, and finally merges the two sorted halves.
• Closest Pair of Points The problem is to find the closest pair of points in a set of
points in the x-y plane. The problem can be solved in O(n^2) time by calculating
the distances of every pair of points and comparing the distances to find the
minimum. The Divide and Conquer algorithm solves the problem in O(N log N)
time.
• Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A simple
method to multiply two matrices needs 3 nested loops and is O(n^3). Strassen’s
https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 6/9
4/1/25, 12:09 PM Evernote

algorithm multiplies two matrices in O(n^2.8974) time.

• 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(N log N)
time.
• Karatsuba algorithm for fast multiplication does the multiplication of two binary
strings in O(n1.59) where n is the length of binary string.

ADVANTAGES :
• Solving difficult problems: Divide and conquer technique is a tool for solving difficult problems
conceptually. e.g. Tower of Hanoi puzzle. It requires a way of breaking the problem into sub-
problems, and solving all of them as an individual cases and then combining sub- problems to the
original problem.
• Algorithm efficiency: The divide-and-conquer algorithm often helps in the discovery of efficient
algorithms. It is the key to algorithms like Quick Sort and Merge Sort, and fast Fourier transforms.
• Parallelism: Normally Divide and Conquer algorithms are used in multi-processor machines
having shared-memory systems where the communication of data between processors does not
need to be planned in advance, because distinct sub-problems can be executed on different
processors.
• Memory access: These algorithms naturally make an efficient use of memory caches. Since the
subproblems are small enough to be solved in cache without using the main memory that is
slower one. Any algorithm that uses cache efficiently is called cache oblivious.

Disadvantages of Divide and Conquer Algorithm:

• Overhead: The process of dividing the problem into subproblems and then combining the
solutions can require additional time and resources. This overhead can be significant for
problems that are already relatively small or that have a simple solution.
• Complexity: Dividing a problem into smaller subproblems can increase the complexity of the
overall solution. This is particularly true when the subproblems are interdependent and must be
solved in a specific order.
• Difficulty of implementation: Some problems are difficult to divide into smaller subproblems or
require a complex algorithm to do so. In these cases, it can be challenging to implement a divide
and conquer solution.
• Memory limitations: When working with large data sets, the memory requirements for storing the
intermediate results of the subproblems can become a limiting factor.

Binary Search Algorithm

Binary Search Algorithm is a searching algorithm used in a sorted array by

repeatedly dividing the search interval in half. The idea of binary search is to use
https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 7/9
4/1/25, 12:09 PM Evernote

the information that the array is sorted and reduce the time complexity to O(log N).

Binary searchis a search algorithm used to find the position of a target value within
a sorted array. It works by repeatedly dividing the search interval in half until the
target value is found or the interval is empty. The search interval is halved by
comparing the target element with the middle value of the search space.

Conditions :
• The data structure must be sorted.
• Access to any element of the data structure should take constant time

step-by-step algorithm
• Divide the search space into two halves by finding the middle index “mid”.
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as the next search space.
◦ If the key is smaller than the middle element, then the left side is used for next search.
◦ If the key is larger than the middle element, then the right side is used for next search.
• This process is continued until the key is found or the total search space is exhausted.

The Binary Search Algorithm can be implemented in the following two ways
• Iterative Binary Search Algorithm
• Recursive Binary Search Algorithm
Iterative Binary Search Algorithm:
Here we use a while loop to continue the process of comparing the key and splitting the search
space in two halves.

Recursive Binary Search Algorithm:

Create a recursive function and compare the mid of the search space with the key. And based on
the result either return the index where the key is found or call the recursive function for the next
search space.

Introduction to NP Hard and NP-Completeness

a159262902029.pdf 1 of 46 pages •

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 8/9
4/1/25, 12:09 PM Evernote

https://lite.evernote.com/note/5eebb383-880e-f176-2b69-6d26924653af 9/9