R.

B Institute of management studies

Subject Name: Analysis and Design of Algorithms
Subject Code: 2688603
Unit-1
What is an 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.
The study of Algorithm, therefore, gives us a language to express
performance as a function of problem size

Need of Algorithm
[Link] understand the basic idea of the problem.

2. To find an approach to solve the problem.

3. To improve the efficiency of existing techniques.

4. To understand the basic principles of designing the algorithms.

[Link] compare the performance of the algorithm with respect to other

techniques.

6. It is the best method of description without describing the

implementation detail.
7. The Algorithm gives a clear description of requirements and goal of
the problem to the designer.

8. A good design can produce a good solution.

9. To understand the flow of the problem.

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

10. To measure the behavior (or performance) of the methods in all
cases (best cases, worst cases, average cases)

Advantages of an Algorithm
 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 Algorithm
 Developing algorithms for complex problems would be time-
consuming and difficult to understand.
 It is a challenging task to understand complex logic through
algorithms.

Analysis of algorithm
The analysis is a process of estimating the efficiency of an algorithm.
There are two fundamental parameters based on which we can analysis
the algorithm:

Space Complexity: The space complexity can be understood as the

amount of space required by an algorithm to run to completion.

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Time Complexity: Time complexity is a function of input size n that
refers to the amount of time needed by an algorithm to run to
completion.

The running time is measured in terms of a particular piece of

hardware, not a robust measure. When we run the same algorithm on a
different computer or use different programming languages, we will
encounter that the same algorithm takes a different time.

Worst-case time complexity: For 'n' input size, the worst-case time
complexity can be defined as the maximum amount of time needed by
an algorithm to complete its execution. Thus, it is nothing but a function
defined by the maximum number of steps performed on an instance
having an input size of n.

Average case time complexity: For 'n' input size, the average-case
time complexity can be defined as the average amount of time needed
by an algorithm to complete its execution. Thus, it is nothing but a
function defined by the average number of steps performed on an
instance having an input size of n.

Best case time complexity: For 'n' input size, the best-case time
complexity can be defined as the minimum amount of time needed by
an algorithm to complete its execution. Thus, it is nothing but a function
defined by the minimum number of steps performed on an instance
having an input size of n.

Benefits of Analysis of Algorithm:

 Performance Optimization: By analyzing algorithms,

developers can identify inefficiencies and bottlenecks, leading to
optimized solutions. Understanding the time and space
complexity of algorithms helps in selecting the most efficient
approach for a given problem, leading to faster and more
responsive software.
 Resource Utilization: Analysis of algorithms helps in better
managing computational resources such as CPU time, memory,
ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA
 and storage. By choosing algorithms with lower time and space
complexities, developers can minimize resource usage, enabling
more efficient utilization of hardware resources.
 Scalability: Algorithms that have been analyzed and optimized
for performance are more scalable, capable of handling larger
datasets and increasing workloads without significant
degradation in performance. Scalable algorithms are essential for
applications that need to accommodate growing user bases and
data volumes over time.
 Predictability: Understanding the behavior of algorithms under
different conditions allows developers to predict their
performance and behavior accurately. This predictability is
crucial for estimating system requirements, planning capacity,
and ensuring that software meets performance expectations in
production environments.
 Selection of Best Solutions: Through comparative analysis,
developers can evaluate multiple algorithms for solving the same
problem and choose the one that best meets the application’s
requirements. Factors such as time complexity, space complexity,
stability, and ease of implementation are considered during the
selection process.
 Debugging and Optimization: Analysis of algorithms provides
insights into the inner workings of algorithms, making it easier to
debug and optimize code. By understanding how algorithms
manipulate data and make decisions, developers can identify and
fix errors more effectively and fine-tune performance where
necessary.

Algorithm Design Techniques

[Link] 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.
 Solve every subproblem individually, recursively.
 Combine the solution of the subproblems (top level) into a
solution of the whole original problem.
ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA
[Link] 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.
[Link] 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.

[Link] 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.

[Link] Algorithms: 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.

[Link] 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.

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Randomized Algorithm: A randomized algorithm uses a random
number at least once during the computation make a decision.

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

Asymptotic Notations
Asymptotic notations are the mathematical notations used to describe
the running time of an algorithm when the input tends towards a
particular value or a limiting value. For example: In bubble sort, when
the input array is already sorted, the time taken by the algorithm is
linear i.e. the best case. But, when the input array is in reverse
condition, the algorithm takes the maximum time (quadratic) to sort the
elements i.e. the worst case. When the input array is neither sorted nor
in reverse order, then it takes average time. These durations are denoted
using asymptotic notations.

There are mainly three asymptotic notations:

➢ Big-O notation

➢ Omega notation

➢ Theta notation

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an
algorithm.

✓ Thus, it gives the worst-case complexity of an algorithm

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Example:

Consider the following f(n) and g(n)...

f(n) = 3n + 2

g(n) = n

If we want to represent f(n) as O(g(n)) then it must satisfy f(n) <= C

g(n) for

all values of C > 0 and n0>= 1

f(n) <= C g(n)

⇒3n + 2 <= C n

Above condition is always TRUE for all values of C = 4 and n >= 2.

By using Big - Oh notation we can represent the time complexity as

follows... 3n + 2 = O(n).

Omega Notation (Ω-notation)

Omega notation represents the lower bound of the running time of an
algorithm. Thus, it provides the best case complexity of an algorithm

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Example:

Consider the following f(n) and g(n)...

f(n) = 3n + 2

g(n) = n

If we want to represent f(n) as Ω(g(n)) then it must satisfy f(n) >= C

g(n) for

all values of C > 0 and n0>= 1

f(n) >= C g(n)

⇒3n + 2 >= C n

Above condition is always TRUE for all values of C = 1 and n >= 1.

By using Big - Omega notation we can represent the time complexity

as

follows...

3n + 2 = Ω(n)

Theta Notation (Θ-notation)

Theta notation encloses the function from above and below.
ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA
Since it represents the upper and the lower bound of the running time
of an algorithm, it is used for analyzing the average-case complexity of
an algorithm.

Consider the following f(n) and g(n)...

f(n) = 3n + 2

g(n) = n

If we want to represent f(n) as Θ(g(n)) then it must satisfy C1 g(n) <=

f(n) <=

C2 g(n) for all values of C1 > 0, C2 > 0 and n0>= 1

C1 g(n) <= f(n) <= C2 g(n)

⇒C1 n <= 3n + 2 <= C2 n

Above condition is always TRUE for all values of C1 = 1, C2 = 4 and

n >= 2.

By using Big - Theta notation we can represent the time compexity as

follows...

3n + 2 = Θ(n)

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Pseudocode Conventions
Pseudocode is a high-level description of an algorithm that uses natural
language mixed with some programming language-like constructs. It
provides a step-by-step outline of the algorithm’s logic without being
tied to any specific programming language syntax. Pseudocode allows
algorithm designers to express their ideas in a concise and
understandable manner before actual coding takes place.

Here's an introduction to some common pseudocode conventions

Readability and Consistency

Use consistent indentation to indicate control structures (e.g., loops

and conditionals).

• Be mindful of whitespace and line breaks to improve readability.

• Choose a clear and consistent naming convention for variables and

functions.

Use of Keywords
Employ standardized keywords to denote common programming
constructs.

Examples include “if,” “while,” “for,” “else,” “return,” and

“function.”

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

 Comments and Annotations
Include comments or annotations to explain complex or non-obvious
parts of the pseudocode.
Comments should provide insight into the logic and purpose of the
code.

Modularization
Break down complex algorithms into smaller, manageable functions
or procedures.
Use clear and meaningful function names to describe their purpose

Difference between Algorithm and the Pseudocode

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA

Characteristic
s Algorithm Pseudocode

A step-by-step procedure A high-level representation of a

to solve a problem or program or algorithm using natural
Definition achieve a specific goal language and structural conventions

To provide a clear and To provide a detailed and structured

concise description of a representation of an algorithm,
Purpose solution to a problem making it easier to implement

Typically written in a structured,

Can be described in English-like language, using
natural language, keywords and syntax similar to
Language flowcharts, or other forms programming languages

High-level, focusing on Lower-level, focusing on the specific

Level of the overall approach and steps and data structures required to
Abstraction logic implement the algorithm

More technical, requiring some

Easy to understand for programming knowledge to
Readability non-technical stakeholders understand

Not directly Can be directly translated into a

Implement implementable in a programming language, with some
ability programming language modifications

No specific syntax, can be Has a specific syntax, with

Syntax described in various forms indentation, keywords, and symbols

"To find the maximum FOR each element in array DO IF

value in an array, iterate element > max THEN max =
through the array and keep element ENDIF ENDFOR
Example track of the largest value" RETURN max

Focuses on the specific steps and data

Focuses on the overall structures required to implement the
Focus logic and approach algorithm

ANALYSIS AND DESIGN ALGORITHM POOJA BHADAURIYA