Design & Analysis of Algorithm

Unit II

Analysis of Algorithms and Complexity Theory

By Prof. Bhavana A. Khivsara

U2: Analysis of Algorithms and Complexity Theory

Syllabus:

• Analysis: Input size, best case, worst case, average case

Counting Dominant operators, Growth rate, upper bounds

• asymptotic growth, O, Ω, Ɵ, o and ω notations
• polynomial and non-polynomial problems, deterministic and non-deterministic algorithms, P- class problems, NP-class of problems, Polynomial problem reduction NP complete problems- vertex cover and 3-SAT and NP hard problem - Hamiltonian cycle.

​

Analysis

Input Size:

Input size (number of elements in the input)

• Running time depends on input size
• Measure time efficiency as function of input size
• Different input of size n may take a different amount of time

​

How do we determine the input size?

​

​

​

​

​

1. A natural parameter
2. For sorting and other problems on array: Array size
3. For combinatorial problems: No of objects
4. For graphs: no of vertices and edges

The compile time does not depend on the instance characteristics. But run time is depending on the instance characteristics.

f(n) :Where n denotes the instance characteristics

​

​

​

​

​

​

​

Types of Analysis

Efficiency of algorithms, is known as analysis of algorithms.

The function f(n), gives the running time of an algorithm, depends not only on the size ‘n’ of the input data but also on the particular data.

The complexity function f(n) for certain cases are:

​

Cont…

1. Best Case : The minimum possible value of f(n) is called the best case.
• Provides a lower bound on running time
• Input is the one for which the algorithm runs the fastest

2. Worst Case : The maximum value of f(n) for any key possible input.

• Provides an upper bound on running time
• An absolute guarantee that the algorithm would not run longer, no matter what the inputs are

3. Average Case : The expected value of f(n).

• Provides a prediction about the running time
• Assumes that the input is random

Example- Linear Search

Example- Linear Search

Example- Sorting

Example- Sorting

�Rate of Growth �

Asymptotic Growth

​

• It is mathematical way of representing the time complexity.
• To compare two algorithms with running times f(n) and g(n), we need a rough measure that characterizes how fast each function grows. [Use rate of growth]
• Compare functions in the limit, that is, asymptotically!

(i.e., for large values of n)

​

Asymptotic Growth

​

• O notation: asymptotic “less than”:
• f(n)=O(g(n)) implies: f(n) “≤” g(n)
• Ω notation: asymptotic “greater than”:
• f(n)= Ω (g(n)) implies: f(n) “≥” g(n)
• Θ notation: asymptotic “equality”:
• f(n)= Θ (g(n)) implies: f(n) “=” g(n)

​

Big-O Notation

• We say f_A(n) = 30n + 8 is order n, or O (n) �It is, at most, roughly proportional to n.
• f_B(n)= n² + 1 is order n², or O(n²).
• It is, at most, roughly proportional to n².
• In general, any O(n²) function is faster- growing than any O(n) function.

Examples

• n⁴ + 100n² + 10n + 50 is O(n⁴)
• 10n³ + 2n² is O(n³)
• n³ - n² is O(n³)
• constants
• 10 is O(1)
• 1273 is O(1)

​

Big Oh Notation

More Examples

• f(n)=Og(n)

f(n)<=c*g(n)

Let f(n)=2n+3

• 1. 2n+3<=10n ; True ,n>=1 : f(n)=O(n)
• 2. 2n+3<=2n+3n=5n ; True, n>=1 : f(n)=O(n)
• 3. 2n+3<=2n^2+3n^2=5n ^2 ; True, n>=1 : f(n)=O(n^2)

If g(n)=log n then , f(n)=O(log n); not true

So closest func for Big O is f(n)=O(n)

Ω - notation

Examples

• f(n)= Ω g(n)

f(n)>=c*g(n)

Let f(n)=2n+3

• 1. 2n+3>=2n ; True ,n>=1 : f(n)= Ω(n)
• 2. 2n+3>=log n ; True, n>=1 : f(n)= Ω(log n)

If g(n)= n^2 then , f(n)= Ω( n^2); not true

So closest func for Big Ω is f(n)= Ω(n)

​

Θ-notation

• Θ-notation

Θ(g(n)) is the set of functions with the same order of growth as g(n)

​

Examples

• f(n)= Θ g(n)

C1*g(n)<=f(n)<=c2*g(n)

Let f(n)=2n+3

1*n<= 2n+3<=5n ; True ,n>=1 : f(n)= Θ(n)

If g(n)= n^2 then , f(n)= Θ( n^2); not true

If g(n)= log n then , f(n)= Θ( log n); not true

So func is exact equal to f(n)= Θ(n)

​

Little o

• We use o-notation to denote an upper bound that is not asymptotically tight
• We formally define o.g.n// (“little-oh of g of n”) as the set
• o.g.n// D ff .n/ W for any positive constant c>0, there exists a constant n0 > 0 such that 0 f .n/ < cg.n/ for all n n0g :

Complexity Theory

Types of Problem

Problems

Polynomial

Non- Polynomial

Types of Problem

​

• Polynomial- Problems that can be solved by a polynomial time algorithm
• Example-
• Searching o(logn)
• Sorting o(nlogn)
• String Editing o(mn)
• Non Polynomial- Problems for which no polynomial time algorithm is known
• Example-
• Travelling Salesperson
• Knapsack Problem

Types of Problem

​

Types of Algorithm

Algorithm

Deterministic

Non- Deterministic

Types of Algorithm

​

• Deterministic Algorithm-
• Result of every operation is uniquely defined
• For a particular input computer will give always same output
• Can solve problem in Polynomial time
• Can determine the next step of execution
• Example-
• 5 + 3 =8
• Non Deterministic Algorithm-
• For same input, Compiler may produce different output in different runs.
• Can not solve problem in Polynomial time
• Can not determine the next step of execution due to more than one path the algorithm can take
• Example-
• X + Y =21 ( Which 2 numbers sum equal to 21)

Non Deterministic Algorithm

NDC Algorithm:

some of the terms related to the non-deterministic algorithm are defined below:

1. choice(X) : chooses any value randomly from the set X.

2. failure() : denotes the unsuccessful solution.

3. success() : Solution is successful and current thread terminates.

​

Consider the problem of searching for an element x in a given set of elements A[1:n]

​

Non Deterministic search

j= choice(a, n)

if(A[j]==x) then

{ write(j); success(); }

write(0); failure();

​

​

Decision Problem Vs Optimization Problems

P, NP, NP Hard, NP Complete

Computational Complexity Problems

P, NP

• P- Problems that can be solved in Polynomial time (“P Stands for Polynomial”) using deterministic algorithm
• Eg. Searching, Sorting etc.
• NP- It stands for non- deterministic polynomial time.
• It is a collection of decision problems that can be solved by a non-deterministic machine in polynomial time.
• Since deterministic algorithm are just a special case of non-deterministic once,
• we conclude that P is Subset of NP
• NP Class problems can be further categorized into NP-Complete & NP-Hard Problems

NP

P

P Vs NP

NP Complete

​

• NP Complete- A problem is called NP- Complete if
• It belongs to class NP
• Every other problems B in NP can be transformed to A in Polynomial time.
• These 2 facts prove that NP- Complete problems are the hardest problems in Class NP.
• However a solution of any NP-Complete Problem can be verified in Polynomial time but cannot be obtained in Polynomial time.

Relation Between P, NP, NP Hard, NP Complete

​

NP

P

NP

Hard

NP Complete

NP-Hard Vs NP-Complete

Polynomial Problem Reduction

• Let L₁ and L₂ be decision problems.
• Problem L₁ reduces to L₂ (also written as L₁ ≤p L₂)
• if and only if there is a way to solve L₁ by a deterministic polynomial-time algorithm using a deterministic algorithm that solves L₂ in polynomial time.
• ➡️ This implies:
• If we have a polynomial-time algorithm for L₂,
• then we can solve L₁ in polynomial time.

Fig- Reduction in NP- Completeness

Every Problem in NP

Circuit - SAT

CNF- SAT

3- SAT

Vertex Cover/Node Cover

Clique

Set-Cover

Sum of Subset

Hamiltonian Cycle

Knapsack

TSP

Steps to Prove Problem L2 is NP- Complete

Steps to Prove Problem L2 is NP- Hard

1. To show that Problem L2 is NP Hard
2. An NP-Hard decision Problem L2 can be shown to be NP -Complete by exhibiting a Polynomial time non- deterministic algorithm for L2

• Pick a Problem L1 already known to be NP-Hard
• Show how to obtain( in Polynomial time) an instance I’ of L2 from any instance I of L1, such that from solution of I’ we can determine the solution to I ( In polynomial deterministic time)
• Conclude from step 2 that L1 is Reducible to L1
• Conclude from Step 1 and 3 that Problem L2 is also NP Hard.

SAT/Satisfiability Means?

• SAT means Satisfiability
• What is meant by Satisfiability?-
• Let X1, X2…Xn denote boolean variables.
• Denote the negation of Xi. A literal is either a variable or its negation
• A Formula is the propositional calculus is an expression that can be constructed using literals and with operations and, or
• Symbols V denotes or denotes and
• CNF is Formula like (X1 V X2) (X2 V X3)
• Satisfiability problem is to determine whether a formula is true for some assignment of truth values to a variables

Circuit SAT

• This is a problem in which a Boolean circuit is taken as input with single output node.
• And then finds whether there is an assignment of values to the circuit’s input so that we get its output values as “1”.
• This assignment of values is called satisfying assignment

Theorem: Circuit SAT is in NP

• Lets Construct a non-deterministic algorithm, which works in polynomial time.
• In which there is choose() method which can guess the values of inputs and output.
• If answer if 0 output will be No
• If answer is 1 output will be Yes
• If algorithm has output output as “Yes” then we can say that Boolean circuit has satisfying input values.
• Thus we can say that Circuit-SAT is in NP.

What is 3-SAT Problem (Restricted Satisfiability)?

• 3-SAT Problem is the problem of determining the satisfiability of a CNF formula where each clause is limited to at most 3 literals
• Example:

(X1 V X2 V X3) (X2 V X3V X4)

​

​

Prove that 3-SAT is NP Complete

Proof:

1. 3-SAt is NP. Given an assignment we can just check that each clause is covered.
2. 3-SAT is NP- hard, �To Prove this, a reduction from SAT to 3-SAT must be provided.
3. We will transform each clause independently based on its length.

Prove that 3-SAT is NP Complete

Prove that 3-SAT is NP Complete

Prove that 3-SAT is NP Complete

Prove that 3-SAT is NP Complete

Node Cover/Vertex Cover

• Node Cover Problem is to find node cover of minimum size in a given graph.
• The word node cover means each node covers its incident edges.
• Thus by node cover we expect to choose the set of vertices which cover all edges in the graph.

Node Cover/Vertex Cover

• Node Cover for this example is {2,4} of size 2

1

2

3

5

4

Theorem- Node Cover is NP Complete

Proof: To Prove this we require to follow steps given below

1. Take a problem which known to be NP Hard, and if that problem is reducible to Node cover then Node Cover is also NP-Hard
2. Proof that Node Cover is NP
3. If Node is NP and NP-Hard we can say that Node Cover is NP Complete

​

Theorem- Node Cover is NP Complete

Proof: To Prove this we require to follow steps given below

• Take a problem CDP (Clique Decision Problem) which known to be NP Hard, and we try to reduce this problem instance into instance of Node cover.

​

​

Theorem- Node Cover is NP Complete

1

2

3

4

5

Theorem- Node Cover is NP Complete

1

2

3

4

5

1

2

3

4

5

Theorem- Node Cover is NP Complete

1

2

3

4

5

1

2

3

4

5

Theorem- Node Cover is NP Complete

1

2

3

4

5

1

2

3

4

5

Theorem- Node Cover is NP Complete

1

2

3

4

5

1

2

3

4

5

Theorem- Node Cover is NP Complete

1

2

3

4

5

1

2

3

4

5

Graph- G

Clique of Size 3 with Vertex {1,2,3}

Graph- G’

Node Cover of Size 2 with Vertex {4,5}