PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 18:
• 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 𝐴𝐴 = 0𝑚𝑚1𝑚𝑚 𝑚𝑚 ≥ 0}?
Let’s analyze one particular TM 𝑀𝑀:
𝑀𝑀 = “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.”
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) 𝑂𝑂 𝑛𝑛2 [quadratic time]
d) 𝑂𝑂(𝑛𝑛3) [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 𝑐𝑐 > 0,𝑛𝑛0 > 0 such that
𝑓𝑓 𝑛𝑛 ≤ 𝑐𝑐𝑔𝑔 𝑛𝑛 for every 𝑛𝑛 ≥ 𝑛𝑛0
Example: 2𝑛𝑛2 + 12 = 𝑂𝑂(𝑛𝑛3) (𝑐𝑐 = 3, 𝑛𝑛0 = 4)
4/5/2021 CS332 – Theory of Computation 7
Properties of asymptotic notation:
Transitive:
𝑓𝑓 𝑛𝑛 = 𝑂𝑂(𝑔𝑔 𝑛𝑛 ) and 𝑔𝑔 𝑛𝑛 = 𝑂𝑂(ℎ 𝑛𝑛 ) means 𝑓𝑓 𝑛𝑛 = 𝑂𝑂(ℎ 𝑛𝑛 )
Not reflexive:
𝑓𝑓 𝑛𝑛 = 𝑂𝑂(𝑔𝑔 𝑛𝑛 ) does not mean 𝑔𝑔 𝑛𝑛 = 𝑂𝑂(𝑓𝑓 𝑛𝑛 )
Example: 𝑓𝑓 𝑛𝑛 = 2𝑛𝑛2, 𝑔𝑔 𝑛𝑛 = 𝑛𝑛3
Alternative (better) notation: 𝑓𝑓 𝑛𝑛 ∈ 𝑂𝑂(𝑔𝑔 𝑛𝑛 )
4/5/2021 CS332 – Theory of Computation 8
Examples
4/5/2021 CS332 – Theory of Computation 9
• 106 𝑛𝑛3 + 2𝑛𝑛2 − 𝑛𝑛 + 10 =
• 𝑛𝑛 + log𝑛𝑛 =
• 𝑛𝑛 (log𝑛𝑛 + 𝑛𝑛) =
• 𝑛𝑛 =
Little-oh
4/5/2021 CS332 – Theory of Computation 10
If 𝑂𝑂-notation is like ≤, then 𝑜𝑜-notation is like < Example: 2𝑛𝑛2 + 12 = 𝑜𝑜(𝑛𝑛3) (𝑛𝑛0 = 4/𝑐𝑐) 𝑓𝑓 𝑛𝑛 = 𝑜𝑜(𝑔𝑔 𝑛𝑛 ) means: For every constant 𝑐𝑐 > 0, there exists 𝑛𝑛0 > 0 such that
𝑓𝑓 𝑛𝑛 ≤ 𝑐𝑐𝑔𝑔 𝑛𝑛 for every 𝑛𝑛 ≥ 𝑛𝑛0
True facts about asymptotic expressions
Which of the following statements is true about the
function 𝑓𝑓 𝑛𝑛 = 2𝑛𝑛?
a) 𝑓𝑓 𝑛𝑛 = 𝑂𝑂 3𝑛𝑛
b) 𝑓𝑓 𝑛𝑛 = 𝑜𝑜 3𝑛𝑛
c) 𝑓𝑓 𝑛𝑛 = 𝑂𝑂 𝑛𝑛2
d) 𝑛𝑛2 = 𝑂𝑂(𝑓𝑓 𝑛𝑛 )
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:
• 𝑛𝑛𝑂𝑂(1)
• 𝑛𝑛2 + 𝑂𝑂 𝑛𝑛
• 1 + 𝑜𝑜 1 𝑛𝑛
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 𝑎𝑎𝑑𝑑 > 0
• Logarithms. log 𝑎𝑎 𝑛𝑛 = 𝑂𝑂(log 𝑏𝑏 𝑛𝑛) for all constants 𝑎𝑎, 𝑏𝑏 > 0
For every 𝑐𝑐 > 0, log𝑛𝑛 = 𝑜𝑜(𝑛𝑛𝑐𝑐)
• Exponentials. For all 𝑏𝑏 > 1 and all 𝑑𝑑 > 0, 𝑛𝑛𝑑𝑑 = 𝑜𝑜(𝑏𝑏𝑛𝑛)
• Factorial. 𝑛𝑛! = 𝑛𝑛 𝑛𝑛 − 1 ⋯1
By Stirling’s formula,
𝑛𝑛! = 2𝜋𝜋𝑛𝑛
𝑛𝑛
𝑒𝑒
𝑛𝑛
1 + 𝑜𝑜 1 = 2𝑂𝑂(𝑛𝑛 log 𝑛𝑛)
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 𝑓𝑓 ∶ ℕ → ℕ
TIME(𝑓𝑓(𝑛𝑛)) is a set (“class”) of languages:
A language 𝐴𝐴 ∈ TIME(𝑓𝑓(𝑛𝑛)) 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) TIME 𝑓𝑓 𝑛𝑛 ⊆ TIME 𝑔𝑔 𝑛𝑛
b) TIME 𝑔𝑔 𝑛𝑛 ⊆ TIME 𝑓𝑓 𝑛𝑛
c) TIME 𝑓𝑓 𝑛𝑛 = TIME 𝑔𝑔 𝑛𝑛
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 𝑂𝑂 𝑛𝑛2
• 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 𝑀𝑀′: 𝑂𝑂 𝑛𝑛 log𝑛𝑛
Theorem (Sipser, Problem 7.49): If 𝐿𝐿 can be decided in
𝑜𝑜 𝑛𝑛 log𝑛𝑛 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 𝑂𝑂(𝑡𝑡 𝑛𝑛 2)
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
Simulating Multiple Tapes
Implementation-Level Description
On input 𝑤𝑤 = 𝑤𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛
1. Format tape into # �̇�𝑤1𝑤𝑤2 …𝑤𝑤𝑛𝑛# ⊔̇ # ⊔̇ # … #
2. For each move of 𝑀𝑀:
Scan left-to-right, finding current symbols
Scan left-to-right, writing new symbols,
Scan left-to-right, moving each tape head
If a tape head goes off the right end, insert blank
If a tape head goes off left end, move back right
4/5/2021 CS332 – Theory of Computation 23
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 𝑂𝑂(𝑡𝑡 𝑛𝑛 2)
Proof: Time analysis of simulation
• Time to initialize (i.e., format tape): 𝑂𝑂 𝑛𝑛 + 𝑘𝑘
• Time to simulate one step of multi-tape TM: 𝑂𝑂 𝑘𝑘 ⋅ 𝑡𝑡 𝑛𝑛
• Number of steps to simulate: 𝑡𝑡 𝑛𝑛
⇒ Total time:
4/5/2021 CS332 – Theory of Computation 24
Applying the simulation theorem
Suppose 𝐵𝐵 is decidable in time 𝑂𝑂(𝑛𝑛2) on a 3-tape TM.
Then a basic single-tape TM can decide 𝐵𝐵 in time…
a) 𝑂𝑂 𝑛𝑛2
b) 𝑂𝑂(𝑛𝑛3)
c) 𝑂𝑂 𝑛𝑛4
d) 2𝑂𝑂(𝑛𝑛)
4/5/2021 CS332 – Theory of Computation 25
Extended Church-Turing Thesis
Every “reasonable” model of computation can be
simulated by a basic, single-tape TM with only a
polynomial slowdown.
E.g., doubly infinite TMs, multi-tape TMs, RAM TMs
Does not include nondeterministic TMs (not reasonable)
Possible counterexamples? Randomized computation,
parallel computation, DNA computing, quantum
computation
4/5/2021 CS332 – Theory of Computation 26
Space complexity
Space complexity of a TM (algorithm) = maximum number of
tape cells it uses on a worst-case input
Formally: Let 𝑓𝑓 ∶ ℕ → ℕ. A TM 𝑀𝑀 runs in space 𝑓𝑓(𝑛𝑛) if on
every input 𝑤𝑤 ∈ Σ𝑛𝑛, 𝑀𝑀 halts on 𝑤𝑤 using at most 𝑓𝑓(𝑛𝑛) cells
A language 𝐴𝐴 ∈ SPACE(𝑓𝑓(𝑛𝑛)) if there exists a basic single-
tape (deterministic) TM 𝑀𝑀 that
1) Decides 𝐴𝐴, and
2) Runs in time 𝑂𝑂(𝑓𝑓(𝑛𝑛))
4/5/2021 CS332 – Theory of Computation 27
Back to our examples
𝐴𝐴 = 0𝑚𝑚1𝑚𝑚 𝑚𝑚 ≥ 0}
Theorem: Let 𝑠𝑠 𝑛𝑛 ≥ 𝑛𝑛 be a function. Every multi-tape
TM running in time 𝑠𝑠 𝑛𝑛 has an equivalent single-tape TM
running in time 𝑂𝑂(𝑠𝑠(𝑛𝑛))
4/5/2021 CS332 – Theory of Computation 28
BU CS 332 – Theory of Computation
Where we are in CS 332
Time and space complexity
Time and space complexity
Example
Example
Review of asymptotic notation
Properties of asymptotic notation:
Examples
Little-oh
True facts about asymptotic expressions
Asymptotic notation within expressions
FAABs: Frequently asked asymptotic bounds
Time and Space Complexity
Running time analysis
Time complexity classes
Time class containment
Example
Example
Example
Does it matter that we’re using the 1-tape model for this result?
How much does the model matter?
Simulating Multiple Tapes
How much does the model matter?
Applying the simulation theorem
Extended Church-Turing Thesis
Space complexity
Back to our examples