Welcome to AIKTC

Analysis of Algorithm|Introduction

Prof. Nusrat Jahan,

Department of Computer Engineering.
AIKTC – Anjuman-I-Islam’s Kalsekar Technical Campus.
 Introduction to Analysis of Algorithm(Syllabus)
• Performance analysis: space and time complexity
• Growth of function
• Big- Oh, Omega Theta notation
• Mathematical background for algorithm analysis.
• Complexity class: Definition of P, NP, NP-Hard, NP-Complete
• Analysis of selection sort, and insertion sort.
• Recurrences: The substitution method, Recursion tree method,
Master method

A.I. Kalsekar Technical Campus, New Panvel 2

What is an Algorithm?
• The word Algorithm means ” A set of finite rules or instructions to be
followed in calculations or other problem-solving operations
Or
• An Algorithm is a finite set of instructions carried out in a specific order
to perform a particular task.
Or
• A procedure for solving a mathematical problem in a finite number of
steps that frequently involves recursive operations.

• Therefore, Algorithm refers to a sequence of finite steps to solve a

particular problem.

• Algorithms can be simple and complex depending on what you want

to achieve.

A.I. Kalsekar Technical Campus, New Panvel 3

A.I. Kalsekar Technical Campus, New Panvel 4
A.I. Kalsekar Technical Campus, New Panvel 5
 Characteristics:
• Clear and Unambiguous: The algorithm should be clear and unambiguous. Each of its
steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined
inputs. It may or may not take input.
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded
and it should be well-defined as well. It should produce at least 1 output.
• Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
• Feasible: The algorithm must be simple, generic, and practical, such that it can be
executed with the available resources. It must not contain some future technology or
anything.
• Language Independent: The Algorithm designed must be language-independent, i.e.
it must be just plain instructions that can be implemented in any language, and yet the
output will be the same, as expected.

A.I. Kalsekar Technical Campus, New Panvel 6

What is the need of an Algorithm
• To understand the basic idea of the problem.
• To find an approach to solve the problem.
• To improve the efficiency of existing techniques.
• It is the best method of description without describing the
implementation detail.
• The Algorithm gives a clear description of requirements and goal of the
problem to the designer.
• A good design can produce a good solution.
• To understand the flow of the problem.
• To measure the behavior (or performance) of the methods in all cases
(best cases, worst cases, average cases)
• To understand the principle of designing.
A.I. Kalsekar Technical Campus, New Panvel 7
How to write an effective Algorithm?
Step – 1 : Obtain detailed information on the problem.
Step – 2 : Analyze the problem.
Step – 3 : Think of a problem-solving approach.
Step – 4 : Review the problem-solving approach and try to think of a
better Alternative.
Step – 5 : Develop a basic structure of the Algorithm.
Step – 6 : Optimize, Improve and refine.

A.I. Kalsekar Technical Campus, New Panvel 8

Example Algorithms
Example of a real-life situation for creating algorithm. Here is the algorithm for
going to the market to purchase a pen.
[Link] dressed to go to the market.
[Link] your wallet for money.
[Link] there is no money in the wallet, replenish it.
[Link] to the shop.
[Link] for your favourite brand of pen.
[Link] Pen is available, go to step 7 else go to step 10.
[Link] money to the shopkeeper.
[Link] the purchased pen safely.
[Link] back home.
[Link] for any other brand of pen.
[Link] to step 7.
A.I. Kalsekar Technical Campus, New Panvel 9
Let us now write an algorithm to check whether a number is positive or
negative .

A.I. Kalsekar Technical Campus, New Panvel 10

Example: Write an algorithm that multiplies two numbers
and displays the output.

• Step 1 − Start
• Step 2 − declare three integers x, y & z
• Step 3 − define values of x & y
• Step 4 − multiply values of x & y
• Step 5 − store result of step 4 to z
• Step 6 − print z
• Step 7 − Stop

A.I. Kalsekar Technical Campus, New Panvel 11

Example: Algorithm to find sum of two Numbers

1. Start
2. Read first number as a
3. Read second number as b
4. Calculate their sum as
Sum= a+b
5. Display sum
6. Stop

A.I. Kalsekar Technical Campus, New Panvel 12

Example: Algorithm to find larger of two numbers

1. Start 1. Start
2. Read first number as x 2. Declare variable x, y, larger
3. Read second number as y 3. Read 1st and 2nd number as x
4. If x>y then larger=x else and y
larger=y 4. If x>y then larger=x else
5. Display larger larger=y
6. stop 5. Display larger
6. stop

A.I. Kalsekar Technical Campus, New Panvel 13

Difference between Algorithm and program

Algorithm Program
1. At design phase 1. At implementation phase
2. Natural language 2. Written any programming
3. Person should have domain language
knowledge 3. Programmer
4. Analyze 4. Testing

A.I. Kalsekar Technical Campus, New Panvel 14

To solve a given problem, you create an algorithm.
A problem can be solved in a variety of ways.

A.I. Kalsekar Technical Campus, New Panvel 15

Types of Algorithms

1. Divide and Conquer Algorithm

2. Greedy Algorithm

3. Dynamic Programming Algorithm

[Link] Algorithm

5. Branch and Bound Algorithm

A.I. Kalsekar Technical Campus,

16
New Panvel
Performance Analysis of an algorithm
• An algorithm is a set of instructions to solve a particular problem.
There can be multiple solutions for a single problem.
• The performance of an algorithm is determined by the resource
required by an algorithm to perform a particular task.
• The most common resources taken into consideration for
determining the performance of an algorithm are:
• Time: The time required to complete the task of that algorithm
(Time Complexity)
• Space: Space required by the program and data (Space
Complexity)

A.I. Kalsekar Technical Campus, New Panvel 17

Asymptotic Notations
➢ Big Oh (O)
➢ Big Omega (Ω)

➢ Theta (Ɵ) Notation

• Big Oh (O) -----→Upper bound----→Maximum time---→Worst case

• Big Omega (Ω) --------→Lower bound ---→Minimum time---→Best case

• Theta (Ɵ) Notation -----→Average time---→Average case

A.I. Kalsekar Technical Campus, New Panvel 18

Graphical Representation of Big-O notation

Big-O gives the upper bound of a

function

Definition: f(n) = O(g(n)) iff there exist

positive constants c and n0 such that
f(n) ≤ cg(n) for all n, n ≥ n0, c>0,
n0>=1.

A.I. Kalsekar Technical Campus, New Panvel 19

 Big Oh Notation (O)
• Definition: f(n) = O(g(n)) iff there exist positive constants
c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0.

• Examples
➢ 3n+2=O(n) /* 3n+2≤4n for n≥2 */
➢ 3n+3=O(n) /* 3n+3≤4n for n≥3 */
➢ 100n+6=O(n) /* 100n+6≤101n for n≥6 */
➢ 10 𝑛2 +4n+2=O(𝑛2 ) /* 10𝑛2 +4n+2≤11 𝑛2 for n≥5 */
➢ 6* 2𝑛 + 𝑛2 =O(2𝑛 ) /* 6* 2𝑛 + 𝑛2 ≤7* 2𝑛 for n≥4 */

A.I. Kalsekar Technical Campus, New Panvel 20

 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.

• Omega gives the lower bound of a

function

A.I. Kalsekar Technical Campus, New Panvel 21

Big Omega (Ω) Notation

A.I. Kalsekar Technical Campus, New Panvel 22

 Theta Notation (Θ-notation)
• Theta notation encloses the function
from above and below. 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.

• Theta bounds the function within

constants factors

A.I. Kalsekar Technical Campus, New Panvel 23

Theta Notation (Ɵ)

A.I. Kalsekar Technical Campus, New Panvel 24

A.I. Kalsekar Technical Campus, New Panvel 25
Figure 1:Plot of function values

• O(1): constant
• O(n): linear
• O(𝑛2 ): quadratic
• O(𝑛3 ): cubic
• O(2𝑛 ): exponential
• O(logn)
• O(nlogn)

A.I. Kalsekar Technical Campus, New Panvel 26

A.I. Kalsekar Technical Campus, New Panvel 27
// O(n2)
for(let i=0; i<n; i++) {
for(let j=0; j<n; j++) // O(n4)
{ for(let i=0; i<n; i++) {
[Link](i, j); for(let j=0; j<n; j++) {
} for(let k=0; k<n; k++) {
} for(let l=0; l<n; l++) {
[Link](i, j, k, l);
}
}
}
}

A.I. Kalsekar Technical Campus, New Panvel 28

If we can not write polynomial time algorithm for exponential time algorithm then we can write non deterministic
algorithm(NP class)
Algorithm

Polynomial Time Non Polynomial Time/

Exponential time

Linear Search(O(n)) 0/1 Knapsack -2𝑛

Binary Search (O(logn)) Travelling salesman-2𝑛

Graph Coloring-2𝑛
Insertion Sort (O(𝑛2 ))
Su-Du-Ku-2𝑛
Merge Sort (O(nlogn))
Scheduling-2𝑛
So we always try to solve exponential time algorithm into polynomial time algorithm.
29
Deterministic Algorithms Non-deterministic Algorithms
It has a single outcome. It has multiple outcomes.

In non-deterministic algorithm most of the

In a deterministic algorithm, all the statements are statements are cleared but some statements are not
cleared. cleared about how they [Link] future some body
may find about how they work.

It has a unique value. It has different values.

Can solve the problem in polynomial time. Can’t solve the problem in polynomial time.

Example : Mathematical function is Example: Random function is non-

deterministic. deterministic.

A.I. Kalsekar Technical Campus, New Panvel 30

Complexity Classes
• In computer science, there exist some problems whose solutions are not yet found,
the problems are divided into classes known as Complexity Classes.
• These classes help scientists to groups problems based on how much time and
space they require to solve problems and verify the solutions.
• It is the branch of the theory of computation that deals with the resources required
to solve a problem.
• The common resources are time and space, meaning how much time the algorithm
takes to solve a problem and the corresponding memory usage.
• The time complexity of an algorithm is used to describe the number of steps
required to solve a problem, but it can also be used to describe how long it takes to
verify the answer.
• The space complexity of an algorithm describes how much memory is required for
the algorithm to operate.
A.I. Kalsekar Technical Campus, New Panvel 31
Types of Complexity Classes

Complexity Class Characteristic feature

P Easily solvable in polynomial time.

NP Yes, answers can be checked in polynomial time.

All NP-hard problems are not in NP and it takes a

NP-hard
long time to check them.

NP-complete A problem that is NP and NP-hard is NP-complete.

A.I. Kalsekar Technical Campus, New Panvel 32

P Class
➢A problem is said to be Polynomial Problem (P) if it can be solved in polynomial time
using deterministic algorithm, like O(𝑛𝑘 ) , where k is constant.
➢Features:
1. Problems which take polynomial time like O(n), O(n2), O(n3).
2. P problems can be solve and verify in polynomial time.
3. P is often a class of computational problems that are solvable and tractable.
➢This class contains many natural problems like Example :
1. Calculating the greatest common divisor.
2. Finding a maximum matching.
3. Finding maximum element in an array
4. To check whether a string is palindrome or not.
5. Searching and sorting (linear search, binary search, insertion sort, merge sort)

A.I. Kalsekar Technical Campus, New Panvel 33

➢Tractable means that the problems can be solved in theory as well as
in practice.
➢But the problems that can be solved in theory but not in practice are
known as intractable.

A.I. Kalsekar Technical Campus, New Panvel

NP Class
➢The NP in NP class stands for Non-deterministic Polynomial Time.
➢A Problem that can't be solved in polynomial time but can be verifiable in
polynomial time.
➢It is the collection of decision problems that can be solved by a non-
deterministic machine in polynomial time.
➢NP problems are checkable in polynomial time means that given a solution of
a problem , we can check that whether the solution is correct or not in
polynomial time.
➢Example: TSP, Sudoku problem, scheduling problem, 0/1 knapsack
problem etc.

A.I. Kalsekar Technical Campus, New Panvel 35

Sudoku Problem

A.I. Kalsekar Technical Campus, New Panvel 36

Sudoku Problem
• You are given a 9 X 9 sudoku which is assumed to have only one unique solution. Each cell
may contain any one of the characters from '1' to '9' and if it's an empty cell then it will have
the '.' character. Solve the given Sudoku puzzle by filling in the empty cells.

• A sudoku solution must satisfy all of the following rules:

[Link] of the digits from 1-9 must occur exactly once in each row.

[Link] of the digits from 1-9 must occur exactly once in each column.

[Link] of the the digits from 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of
the grid.

A.I. Kalsekar Technical Campus, New Panvel 37

Time Complexity is exponential. But once we have solution then it is easy to check whether
solution is correct or not. So verification can be possible in polynomial time.
A.I. Kalsekar Technical Campus, New Panvel 38
 Venn Diagram of P and NP

So we can say P is the

NP subset of NP class Problems
i.e. P ⊆ NP

Tractable Problems Intractable Problems

A problem that is solvable by A problem that cannot be solved by
a polynomial-time algorithm. a polynomial-time algorithm.
A.I. Kalsekar Technical Campus, New Panvel 39
Example
• Currently we have Binary search algorithm which require logn time.
• So we are trying to find algorithm which require less than the logn
time or Constant time.
• But we can’t find algorithm which require constant [Link] finally we
write Non-deterministic Algorithm for binary search.

A.I. Kalsekar Technical Campus, New Panvel 40

Example

Non Deterministic Algorithm

Deterministic Algorithm
Algorithm Search(A, n, key)
• The algorithm which we {
generally use: like linear i=choice(); O(1): No idea about how it works
search, binary search, If(A[i] ==key) O(1)
where we know that how {
each and every step works.
Print(i) O(1)
//success So total time
} complexity of above
Print(0) O(1) algorithm is O(1). But
it is non deterministic
//failure
algorithm
}
NP-hard class
To understand the NP-Hard first you must know about Reduction.

What is Reduction??????

Suppose we have two decision problems P1 and P2.

Problem:P1 Problem: P2
Input:I1 Input: I2
Algorithm: A?(Not Exist) Algorithm: B(Exist)
Suppose if we can solve P1 problem by using Algorithm of problem P2(i.e. B).Then there is
no need to write algorithm A.
So P1 is reducible to P2 as we can solve P1 problem with the help of Algorithm of P2 problem

It is denoted as : P1α P2, but this conversion cost must be polynomial

Reducability:
➢ Let L1 and L2 are the two problems. L1 is reduced to L2 iff there is a way to
solve L1 by a deterministic polynomial time algorithm using a deterministic
algorithm that solves L2 in polynomial time and is denoted by L1α L2.
➢If we have a polynomial time algorithm for L2 then we can solve L1 in
polynomial time.
➢Two problems L1 and L2 are said to be polynomially equivalent iff L1α L2 and
L2 α L1.

A.I. Kalsekar Technical Campus, New Panvel 43

NP Hard:
• A problem is NP hard if all problems in NP are polynomial time
reducible to it, even though it may not be in NP itself.

A.I. Kalsekar Technical Campus, New Panvel 44

NP-hard class
Features:
[Link] NP-hard problems are not in NP.
[Link] takes a long time to check them. This means if a solution for an NP-hard problem
is given then it takes a long time to check whether it is right or not.
[Link] of the examples of problems in Np-hard are:

• Halting problem.
• Qualified Boolean formulas.
• No Hamiltonian cycle.
• Optimization Problem

A.I. Kalsekar Technical Campus, New Panvel 45

 NP-complete class
➢ A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP.

➢ Features:
1. NP-complete problems are special as any problem in NP class can be transformed or reduced into NP-complete
problems in polynomial time.
2. If one could solve an NP-complete problem in polynomial time, then one could also solve any NP problem in
polynomial time.
• Some example problems include:
1. Decision version of 0/1 Knapsack.
2. Hamiltonian Cycle.
3. Satisfiability.
4. Vertex cover.

A.I. Kalsekar Technical Campus, New Panvel 46

A.I. Kalsekar Technical Campus, New Panvel 47
Relationship between
P,NP,NP-hard, NP-Complete

A.I. Kalsekar Technical Campus, New Panvel 48