Microsoft PowerPoint – CS332-Lec19-ann
BU CS 332 – Theory of Computation
Lecture 19:
• Asymptotic Notation
• Time/Space Complexity
Reading:
Sipser Ch 7.1, 8.0
Mark Bun
April 5, 2021
Where we are in CS 332
4/5/2021 CS332 ‐ Theory of Computation 2
Automata Computability Complexity
Previous unit: Computability theory
What kinds of problems can / can’t computers solve?
Final unit: Complexity theory
What kinds of problems can / can’t computers solve under
constraints on their computational resources?
Time and space complexity
Today: Start answering the basic questions
1. How do we measure complexity? (as in CS 330)
2. Asymptotic notation (as in CS 330)
3. How robust is the TM model when we care about
measuring complexity?
4. How do we mathematically capture our intuitive
notion of “efficient algorithms”?
4/5/2021 CS332 ‐ Theory of Computation 3
Time and space complexity
Time complexity of a TM = Running time of an algorithm
= Max number of steps as a function of input length
Space complexity of a TM = Memory usage of algorithm
= Max number of tape cells as a function of input length
4/5/2021 CS332 ‐ Theory of Computation 4
Example
How much time/space does it take for a basic single‐tape
TM to decide ?
Let’s analyze one particular TM :
= “On input :
1. Scan input and reject if not of the form ∗ ∗
2. While input contains both ’s and ’s:
Cross off one and one
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
4/5/2021 CS332 ‐ Theory of Computation 5
Example
𝑀 = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. While input contains both 0’s and 1’s:
Cross off one 0 and one 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
What is the best possible bound you can put on the time complexity of 𝑀?
a) 𝑂 1 [constant time]
b) 𝑂 𝑛 [linear time]
c) 𝑂 𝑛 [quadratic time]
d) 𝑂 𝑛 [cubic time]
What is the space complexity of 𝑀?
4/5/2021 CS332 ‐ Theory of Computation 6
Review of asymptotic notation
‐notation (upper bounds)
means:
There exist constants such that
for every
Example: ( , )
4/5/2021 CS332 ‐ Theory of Computation 7
Properties of asymptotic notation:
Transitive:
and means
Not reflexive:
does not mean
Example:
Alternative (better) notation:
4/5/2021 CS332 ‐ Theory of Computation 8
Examples
4/5/2021 CS332 ‐ Theory of Computation 9
• 6 3 2
•
•
•
Little‐oh
4/5/2021 CS332 ‐ Theory of Computation 10
If ‐notation is like , then ‐notation is like
Example: ( )
means:
For every constant there exists such that
for every
True facts about asymptotic expressions
Which of the following statements is true about the
function ?
a)
b)
c)
d)
4/5/2021 CS332 ‐ Theory of Computation 11
Asymptotic notation within expressions
Asymptotic notation within an expression is shorthand for
“there exists a function satisfying the statement”
Examples:
•
•
•
4/5/2021 CS332 ‐ Theory of Computation 12
FAABs: Frequently asked asymptotic bounds
4/5/2021 CS332 ‐ Theory of Computation 13
• Polynomials. 0 1 𝑑 𝑑 is 𝑑 if 𝑑
• Logarithms.
𝑎 𝑏
for all constants
For every ,
• Exponentials. For all and all , 𝑑 𝑛
• Factorial.
By Stirling’s formula,
Time and Space Complexity
4/5/2021 CS332 ‐ Theory of Computation 14
Running time analysis
Time complexity of a TM (algorithm) = maximum number of
steps it takes on a worst‐case input
Formally: Let . A TM runs in time if on
every input , halts on within at most steps
‐ Focus on worst‐case running time: Upper bound of
must hold for all inputs of length
‐ Exact running time does not translate well between
computational models / real computers. Instead focus on
asymptotic complexity.
4/5/2021 CS332 ‐ Theory of Computation 15
Time complexity classes
Let
is a set (“class”) of languages:
A language if there exists a basic single‐
tape (deterministic) TM that
1) Decides , and
2) Runs in time
4/5/2021 CS332 ‐ Theory of Computation 16
Time class containment
If , then which of the following
statements is always true?
a)
b)
c)
d) None of the above
4/5/2021 CS332 ‐ Theory of Computation 17
Example
𝐴 0 1 𝑚 0
𝑀 = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. While input contains both 0’s and 1’s:
Cross off one 0 and one 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
• runs in time
• Is there a faster algorithm?
4/5/2021 CS332 ‐ Theory of Computation 18
Example
𝐴 0 1 𝑚 0
𝑀′ = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. While input contains both 0’s and 1’s:
• Reject if the total number of 0’s and 1’s remaining is odd
• Cross off every other 0 and every other 1
3. Accept if no 0’s and no 1’s left. Otherwise, reject.”
• Running time of :
• Is there a faster algorithm?
4/5/2021 CS332 ‐ Theory of Computation 19
Example
Running time of :
Theorem (Sipser, Problem 7.49): If can be decided in
time on a 1‐tape TM, then is regular
4/5/2021 CS332 ‐ Theory of Computation 20
Does it matter that we’re using the 1‐tape
model for this result?
It matters: 2‐tape TMs can decide faster
𝑀′′ = “On input 𝑤:
1. Scan input and reject if not of the form 0∗1∗
2. Copy 0’s to tape 2
3. Scan tape 1. For each 1 read, cross off a 0 on tape 2
4. If 0’s on tape 2 finish at same time as 1’s on tape 1, accept.
Otherwise, reject.”
Analysis: is decided in time on a 2‐tape TM
Moral of the story (part 1): Unlike decidability, time
complexity depends on the TM model
4/5/2021 CS332 ‐ Theory of Computation 21
How much does the model matter?
Theorem: Let be a function. Every multi‐tape
TM running in time has an equivalent single‐tape TM
running in time
Proof idea:
We already saw how to simulate a multi‐tape TM with a
single‐tape TM
Need a runtime analysis of this construction
Moral of the story (part 2): Time complexity doesn’t
depend too much on the TM model (as long as it’s
deterministic, sequential)
4/5/2021 CS332 ‐ Theory of Computation 22