[go: up one dir, main page]
Scribd
Upload
49 views21 pages

Chapter 7 Complexity

Uploaded by

abdumulate16
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
49 views21 pages

Chapter 7 Complexity

Uploaded by

abdumulate16
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

Chapter 7

Complexity Theory
Complexity Theory
• Complexity theory is basically the study of what's hard or
easy to solve with a computer.
• The key thing is how the number of steps it takes to solve a
problem grows with the size of the input.
Complexity Theory
Measure of Complexity
• There are two kinds of measures with Complexity Theory:

i. Time Complexity:
– It is a measure of how long a computation takes to execute.

ii. Space Complexity:


– It is a measure of how much storage is required for a
computation.
Big O notation

• Big O notation is a mathematical notation that describes the


limiting behavior of a function when the argument tends
towards a particular value or infinity.
• Big O notation describes the complexity of your code using
algebraic terms.
Order Statistic
• In Complexity theory, equations are subjected to extreme
simplifications.
• If an algorithm takes exactly 50n3 + 5n2 − 5n + 56 machine
cycles, where, ‘n’ is the size of the input, then we shall
simplify this to O(n3). This is called the “order statistic”.
• It is customary to
– Drop all terms except the highest-ordered one
– Drop the co-efficient of the highest-ordered term.
Find the order of the following polynomials:
Types of Time Complexities
 There are different types of time complexities, so let's
check the most basic ones.
 Constant Time Complexity: O(1)

 Linear Time Complexity: O(n)

 Logarithmic Time Complexity: O(log n)

 Quadratic Time Complexity: O(n²)

 Exponential Time Complexity: O(2n)


Examples
 The Time complexity or Big O notations for some popular
algorithms are listed below:
 Binary Search: O(log n)
 Linear Search: O(n)
 Quick Sort: O(n * log n)
 Selection Sort: O(n * n) <html>
 Travelling salesperson : O(n!)
Integer Bin Packing

Assume we are given a set of n integers. Our task is to arrange


these integers into two piles or bins, so that the sum of the integers
in one pile is equal to the sum of the integers in the other pile.

For example, given the integers


Boolean Satisfiability (SAT)

Assume we have n Boolean variables, viz., A, B, C, .... and an


expression in the propositional Calculus i.e., we can use and, or
and not to form the expression.

Is there an assignment of truth values to the variables, (for


example, A = true, B = true, C = false), that will make the
expression true?
SAT Continued….
What are NP, P, NP-complete, and NP-Hard problems?

 P is a set of problems that can be solved by a deterministic Turing machine


in Polynomial-time.
 NP is a set of decision problems that can be solved by a Non-deterministic
Turing Machine in Polynomial-time.
 NP-complete problems are the hardest problems in the NP set.
 A decision problem L is NP-complete if:
 L is in NP.

 Every problem in NP is reducible to L in polynomial time.


 A problem is NP-Hard if it follows property 2 mentioned above, and doesn’t
need to follow property 1.
 Therefore, the NP-Complete set is also a subset of the NP-Hard set.
What are NP, P, NP-complete, and NP-Hard problems?
Polynomial-time Algorithms

• A polynomial-time algorithm is an algorithm whose execution


time is either given by a polynomial on the size of the input.

• Problems which can be solved by a polynomial-time algorithm


are called “tractable” problems.

• Example:

– Sorting algorithms

– All programming tasks


Non-deterministic Polynomial Time Algorithms(NP – Problems)

• A Non-deterministic Polynomial Time Algorithm is one that can be


executed in polynomial time on a nondeterministic machine.

• There are literally hundreds of examples.


 The Travelling Salesman Problem (TSP):

 The Hamiltonian Circuit Problem:

 Linear Programming:
NP-complete Problems

All the known NP problems have a remarkable characteristic: They are all

reducible to one another. What this means is that, given any two NP problems

X and Y,

(a) There exists a polynomial-time algorithm to restate a problem of type X as a


problem of type Y, and

(b) There exists a polynomial-time algorithm to translate a solution to a type Y


problem back into a solution for the type X problem.

You might also like