Readings
CIS 121—Data Structures and Algorithms—Spring 2020
Asymptotic Notation—Monday, January 27/Tuesday, January 28
Solution Set
• Lecture Notes Chapter 5: Running Time and Growth Functions Problems
Problem 0 [True or False]
1. A Big-O and Big-Omega bound for an algorithm correspond to worst-case and best-case runtime, respectively.
2. For any two functions, f and g, either f ∈ O(g) or g ∈ O(f).
3. f(n) ∈ O(g(n)) if and only if g(n) ∈ Ω(f(n)).
Solution.
1. False. Big-O notation is a way to describe the limiting behavior of a function. One can provide a Big-O bound on the best, worst, and average case runtimes of an algorithm. It is not inherently tied to a particular one of these different ways to analyze an algorithm’s efficiency. The same is true for Big-Omega.
2. False. Consider sin(x) and cos(x).
3. True. If f(n) ∈ O(g(n)), then we know there exist positive constants c and n0 s.t. for all n ≥ n0
f(n) ≤ c · g(n)
Thus, for c′ = c−1 and n′0 = n0 (both of which are positive), we have for all n ≥ n′0
g(n) ≥ c′ · f(n)
Note: The other direction can be proven in an identical manner.
Problem 1
Prove that 3n2 + 100n = Θ(5n2) Solution
We first prove Big-O. Recall the definition of Big-O—we wish to show that there exist positive constants c andn0 suchthatforalln≥n0,
3n2 +100n≤c·5n2 3n+100 ≤ 5c·n
100 ≤ (5c − 3)n 100 ≤ (5(1) − 3)n 100 ≤ 2n
50 ≤ n 1
(setting c = 1)
Since the expression holds for c = 1 and n0 = 50, we have proved that 3n2 + 100n = O(5n2).
Next, we prove Big-Omega. Recall the definition of Big-Omega—we wish to show that there exist positive constants c and n0 such that for all n ≥ n0,
Therefore, 3n2 + 100n = Θ(5n2). Problem 2
3n2 +100n≥c·5n2
3n2 + 100n ≥ (3/5) · 5n2 3n2 + 100n ≥ 3n2
100n ≥ 0 n≥0
(setting c = 3/5)
Since the expression holds for n0 = 1 and c = 3/5, we have proved that 3n2 + 100n = Ω(5n2). Since 3n2 + 100n = O(5n2) and 3n2 + 100n = Ω(5n2), we have proved that 3n2 + 100n = Θ(5n2). Alternate Limit Solution
lim 3n2 +100n = lim 3n+100
n→∞ 5n2
Prove using induction that n log n = Ω(n) Solution.
Wewillprovethatnlogn≥c·n, ∀n≥n0 byusinginductionforn0 =4andc=1. Base Case: n = 4. 4 log 4 = 8 ≥ 4, so this holds.
Induction Hypothesis: Assume that k log k ≥ k for some integer k ≥ 4. Induction Step: We need to show that (k + 1) log(k + 1) ≥ k + 1.
Problem 3
Prove that lg(n!) = Θ(n lg n). Solution.
We first show lg(n!) = O(n lg n): Pickingc=1andn0 =1,wehave
n
(k + 1) log(k + 1) ≥ (k + 1) log k = k log k + log k
(since log x is monotonically increasing)
(since log k ≥ 2) (by IH)
> k log k + 1 ≥ k + 1
lg(n!) = lgi ≤ nlgn i=1
2
n→∞ 5n = lim 3n
Solution Set
n→∞ 5n = 3/5
This is clearly true for all n ≥ n0.
We then show that lg(n!) = Ω(n lg n):
To start, we find a simple lower-bound for lg n! that we can again lower-bound with some c · n lg n.
lg n! = lg 1 + lg 2 + · · · + lg n
≥ lg n + lg( n + 1) + · · · + lg n (the second half of the terms)
22
≥ n · lg n (since lg x is monotonically increasing) 22
Choosing c = 1 and n0 = 4, it is clear that n lg n ≥ n lgn for all n ≥ n0 with some algebraic manipulation: 4 224
Solution Set
n lg n ≥ n lg n 224
n lg n − n ≥ n lg n 224
nlgn ≥ 2n lg n ≥ 2
Therefore, lg(n!) is also Ω(n lg n).
3