CSE 373 AU20 Section 2
Asymptotics
MicroTeach: Basic Big O
Worse Runtime
...
MicroTeach: Big O
Big O Bound
O(n log n)
Θ(n)
Θ(log n), Θ(1)
Θ(n^2)
Θ(2^n)
Θ(n!)
O(n log n)
Finding a Big-O
We have an expression for 𝑓(𝑛).
Simplify it (if possible).
1. Find the “dominating term” and delete all others.
The “dominating” term is the one that is largest as 𝑛 gets bigger. In this class, often the largest power of 𝑛.
2. Remove any constant factors.
3. Write the final big-O – (basically just putting the O symbol around your remaining n-term)
Dominant Term Rules
�Exponential dominates a polynomial.��Higher order polynomial dominates a lower order one.��Any polynomial dominates a log.��Log dominates constant.����
Important!
In this analysis, we don’t care about leading constants or “smaller” terms.��Why? All of this assumes n → ∞.
Problem 1a, 1b: Comparing growth rates
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
We want to find the complexity class of this overall function but the bases of these two logarithms are different. Are these two logarithms in the same complexity class? Does one dominate the other?
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Using the Change of Base formula, we can convert a logarithm’s base to any number we want!
Change of Base Formula:
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Using the Change of Base formula, we can convert a logarithm’s base to any number we want!
Ex: log4(n) = log2(n) / log2(4)
Note that log2(4) = 2. It’s just a constant and we don’t really care about constants when doing asymptotic analysis (since we assume n → ∞).
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Using the Change of Base formula, we can convert a logarithm’s base to any number we want!
Ex: log4(n) ≈ log2(n)
All logarithms that differ only by a constant base are in the same complexity class! That’s why you’ll often see us omitting the base altogether.
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
= log2(n)/2 + log2(n) = 3/2 * log2(n)
∈ O(log(n))
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Drop constants!
≈ n ∈ O(n)
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Drop constants!
≈ 2n ∈ O(2n)
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
∈ O(1)
Remember that when doing asymptotic analysis, we’re only concerned with what happens to the runtime as n → ∞. Here, our runtime is a constant, which means that it doesn’t depend on our input size n. We use O(1) to represent the family/set of constant functions.
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Higher order polynomials dominate lower order ones. 4n2 dominates 8n as n → ∞ so that’s the term that determines the complexity class of the overall function.
∈ O(n2)
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
1a
Simplify each of the following functions to a tight big-O bound in terms of n. Then order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Ordered from fastest growing to slowest:
O(2n)
≥ O(n2)
≥ O(n)
≥ O(log(n))
≥ O(1)
Note: Code in this complexity class takes longer to execute than the others!
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Tricky! Constant multipliers don’t matter in big-O notation, but they do in an exponent. Why? Because it’s not really a constant factor.
∈ O(2n)
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Tricky! Constant multipliers don’t matter in big-O notation, but they do in an exponent. Why? Because it’s not really a constant factor.
Ex: 22n = 2n⋅2n
The 2 in the exponent actually means multiplying by 2n, which we can’t ignore!
Multiplying exponents:
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
This is a different complexity class entirely!
Note: xn grows at a strictly faster rate than any yn where x > y.
∈ O(3n)
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Same thing. It’s it’s own complexity class.
∈ O(2n)
1b
State a tight big-O bound for each of the following functions and order them from the fastest growing to slowest growing (“fastest function” meaning the one that increases the most rapidly as n increases).
Ordered from fastest growing to slowest:
O(3n) ≥ O(2n) ≥ O(2n/2)
Problems 2c, 2d, 2e: True or False?
2d
If a function is in O(n²), then it is always in O(n)
What does O(n²) mean for our function?
The function will grow as slow or slower than n²
What does O(n) mean for our function?
The function will grow as slow or slower than n
False
2e
If a function is in O(n), then it is always in O(n²)
What does O(n) mean for our function?
The function will grow as slow or slower than n
What does O(n²) mean for our function?
The function will grow as slow or slower than n²
True
MicroTeach: Big O Code Modeling
Code Big-O Analysis
Indicate the big-O runtime for the following code.
Code Big-O Analysis
Indicate the big-O runtime for the following code.
Problem 4 a
Problem 4a)
int x = 0;
for (int i= 0; i < n; i++) {
for (int j = 0; j < n* n /3; j++) {
X += j;
}
}
Step 1) Analyze
int x = 0; Constant Work
for (int i= 0; i < n; i++) {
for (int j = 0; j < n* n /3; j++) {
X += j;
}
}
Problem 4a)
int x = 0;
for (int i= 0; i < n; i++) { Operates N times
for (int j = 0; j < n* n /3; j++) {
X += j;
}
}
Problem 4a)
int x = 0;
for (int i= 0; i < n; i++) {
for (int j = 0; j < n* n /3; j++) { Operates
X += j; (N^2)/3 times
}
}
Problem 4a)
int x = 0;
for (int i= 0; i < n; i++) {
for (int j = 0; j < n* n /3; j++) {
X += j; Constant Work
}
}
Problem 4a)
POSSIBLE RUNTIME:
T(N) = (N ^3) /3
WORST CASE RUNTIME:
O (N^ 3)
(N^3)/3 = ⅓ * (N^3)
DROP CONSTANT !
Problem 4 b
Problem 4b)
int x = 0;
for (int i = n; i >= 0; i -= 1) {
if (i % 3 == 0) {
break;
} else {
x += n;
}
}
int x = 0;
for (int i = n; i >= 0; i -= 1) {
if (i % 3 == 0) {
break;
} else {
x += n;
}
}
int x = 0;
for (int i = n; i >= 0; i -= 1) {
if (i % 3 == 0) {
break;
} else {
x += n;
}
}
+1
+1
+1
+2
What about the for loop??
At most it can only run 3 times!
So the entire for loop is equivalent to 3 * the inside of the loop body!
3 * 4 =
+12
+4
Problem 4b)
POSSIBLE RUNTIME:
T(N) = 13
WORST CASE RUNTIME:
O (1)
Discussion: Case Analysis of 4a and 4b
The runtimes of both methods do not change based on the case. The only relevant variable in both is the input number so there is only one possible code model. There is nothing else barring the performance of either method, both are completely dependent on the size of N. If you think about it, even in the best case, 4a will be O(N^3) and 4b will be O(1). So these runtimes are representative for ALL CASES, not just the worst case. Cool!
Challenge Problem!
Challenge Problem
We want to implement a calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators, and empty spaces. The integer division should truncate toward zero. You can assume that the input will be always in a valid format.
Sample Test Cases:
Input: “2 * 5 + 3”
Output: 13
Input: “16 / 14”
Output: 1
Input: “2+ 14 / 7”
Output: 4
Solution for Challenge Problem
divide
Solution for Challenge Problem
Solution for Challenge Problem
Solution for Challenge Problem
Solution to Challenge Problem
https://docs.google.com/document/d/1pxjgqbphFlOhA7cxFRIAyrKWl58Bj4EcLk5dMJhWTYw/edit?usp=sharing