CSC165H1, Winter 2022 CSC165H1: Worksheet 11—Introduction to Big-O Notation (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove and disprove statements using the definition of Big-O.
Copyright By PowCoder代写 加微信 powcoder
• Investigate properties of Big-O for some common families of functions.
Note: In Big-O expressions, it will be convenient to just write down the “body” of the functions rather than defining named functions all the time. We’ll always use the variable n to represent the function input, and so when we write “n ∈ O(n2),” we really mean “the functions defined as f(n) = n and g(n) = n2 satisfy f ∈ O(g).”
As a reminder, here is the formal definition of Big-O:
g∈O(f): ∃c,n0 ∈R+, ∀n∈N, n≥n0⇒g(n)≤cf(n) wheref,g:N→R≥0
1. Comparing polynomials. Our first step in comparing different families of functions is looking at different powers of n. Consider the following statement, which generalizes the fact that n ∈ O(n2):
∀a,b∈R+, a≤b⇒na ∈O(nb) (a) Rewrite the above statement by expanding the definition of Big-O.
(b) Prove the above statement. Hint: you can actually pick c and n0 to both be 1. Even though this is pretty simple, take the time to write the formal proof as a good warm-up for the rest of this worksheet.
∀a,b∈R+, a≤b⇒∃c,n0 ∈R+, ∀n∈N, n≥n0 ⇒na ≤cnb
Proof. Leta,b∈R+,andassumea≤b. Letc=1andn0 =1. Letn∈N,andassumethatn≥n0. We want to prove that na ≤ nb.
We can start with our assumption that a ≤ b and calculate:
na ≤nb (sincen≥1) na ≤cnb (sincec=1)
Note: going from a ≤ b to na ≤ nb involves raising n to the power of both sides. This is valid when n ≥ 1.
2. Comparing logarithms. One slight oddity about the definition of Big-O is that it treats all logarithmic functions “the same”. Your task in this question is to investigate this by proving the following statement:1
∀a,b∈R+, a>1∧b>1⇒logan∈O(logbn)
We won’t ask you to expand the definition of Big-O, but if you aren’t quite sure, then we highly recommend doing
so before attempting even your rough work!
Hint: use the “change of base rule” for logarithms.
1If you are concerned by the fact that log n is not defined at n = 0, you can replace loga n with loga(1 + n) in the above, and similarly with logb. We usually don’t worry about this subtlety, since our concern is with the value of the functions for larger values of n. Picking an n0 > 0 avoids the evaluation worry.
CSC165H1, Winter 2022 CSC165H1: Worksheet 11—Introduction to Big-O Notation (Partial Solutions)
Proof. Leta,b∈R+. Assumethata>1andb>1. Letn0 =1,andletc= 1 .∗ Letn∈N,andassume
thatn≥n0. Wewanttoshowthatlogan≤c·logbn. The logarithm change of base rule tells us the following:†
Using this rule, we can write:
∀a,b,x∈R+, a̸=1∧b̸=1⇒logax= logbx logb a
loga n = logb n logb a
= 1 logbn logb a
= c · logb n
Since we’ve proved that loga n = c · log bn, we can conclude that loga n ≤ c · logb n.
[Note: we didn’t need to use the assumption that n ≥ 1 in this proof.]
∗Since a,b > 1, we know that c > 0.
†When the bases are equal to 1, loga x is undefined when x ̸= 1.
CSC165H1, Winter 2022 CSC165H1: Worksheet 11—Introduction to Big-O Notation (Partial Solutions)
3. Sum of functions. Now let’s look at one of the most important properties of Big-O: how it behaves when adding functions together. Let f,g : N → R≥0. We define the sum of f and g as the function f +g : N → R≥0 such that ∀n ∈ N, (f + g)(n) = f(n) + g(n). For example, if f(n) = 2n and g(n) = n2 + 3, then (f + g)(n) = 2n + n2 + 3.
Consider the following statement:
∀f,g:N→R≥0, g∈O(f)⇒f+g∈O(f)
In other words, if g is Big-O of f , then f + g is no bigger than just f itself, asymptotically speaking.
Your task for this question is to prove this statement. Keep in mind this is an implication: you’re going to assume that g ∈ O(f), and you want to prove that f + g ∈ O(f). It will likely be helpful to write out the full statement (with the definition of Big-O expanded), and use subscripts to help keep track of the variables.
Here’s the full statement, with the definitions expanded:
∀f,g:N→R≥0, ∃c,n0 ∈R+, ∀n∈N, n≥n0 ⇒g(n)≤cf(n)⇒
∃c1,n1 ∈R+, ∀n∈N, n≥n1 ⇒f(n)+g(n)≤c1f(n)
Proof. Let f,g : N → R≥0. Assume that g ∈ O(f), i.e., there exist n0,c ∈ R+ such that for all natural numbers
n,ifn≥n0 theng(n)≤cf(n). Wewanttoprovethatf+g∈O(f).
Let n1 = n0, and c1 = c+1. Let n ∈ N, and assume that n ≥ n1. We want to prove that f(n)+g(n) ≤ c1f(n). Since n ≥ n1 = n0, by our assumption we know that g(n) ≤ cf(n). So then:
g(n) ≤ cf(n)
f(n) + g(n) ≤ f(n) + cf(n)
f(n) + g(n) ≤ (c + 1)f(n) f(n) + g(n) ≤ c1f(n)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com