xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

有限状态过程代写-CSC165H1

时间：2021-04-05

CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)

Learning Objectives

By the end of this worksheet, you will:

• Prove and disprove statements using the definition of Big-Oh.

• Investigate properties of Big-Oh for some common families of functions.

Note: In Big-Oh 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-Oh:

g ∈ O(f) : ∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ g(n) ≤ cf(n) where f, 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-Oh.

Solution

∀a, b ∈ R+, a ≤ b⇒

(

∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ na ≤ cnb

)

(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.

Solution

Proof. Let a, b ∈ R+, and assume a ≤ b. Let c = 1 and n0 = 1. Let n ∈ N, and assume that n ≥ n0. We

want to prove that na ≤ nb.

We can start with our assumption that a ≤ b and calculate:

a ≤ b

na ≤ nb (since n ≥ 1)

na ≤ cnb (since c = 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-Oh 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⇒ loga n ∈ O(logb n)

We won’t ask you to expand the definition of Big-Oh, 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 logn 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.

Page 1/3

CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)

Solution

Proof. Let a, b ∈ R+. Assume that a > 1 and b > 1. Let n0 = 1, and let c = 1

logb a

.∗ Let n ∈ N, and assume

that n ≥ n0. We want to show that loga n ≤ c · logb n.

The logarithm change of base rule tells us the following:†

∀a, b, x ∈ R+, a 6= 1 ∧ b 6= 1⇒ loga x =

logb x

logb a

Using this rule, we can write:

loga n =

logb n

logb a

=

1

logb a

logb n

= 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 6= 1.

Page 2/3

CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)

3. Sum of functions. Now let’s look at one of the most important properties of Big-Oh: 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-Oh 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-Oh expanded), and use subscripts to help keep track of the variables.

Solution

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, if n ≥ n0 then g(n) ≤ cf(n). We want to prove that f + 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)

Page 3/3

学霸联盟

Learning Objectives

By the end of this worksheet, you will:

• Prove and disprove statements using the definition of Big-Oh.

• Investigate properties of Big-Oh for some common families of functions.

Note: In Big-Oh 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-Oh:

g ∈ O(f) : ∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ g(n) ≤ cf(n) where f, 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-Oh.

Solution

∀a, b ∈ R+, a ≤ b⇒

(

∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ na ≤ cnb

)

(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.

Solution

Proof. Let a, b ∈ R+, and assume a ≤ b. Let c = 1 and n0 = 1. Let n ∈ N, and assume that n ≥ n0. We

want to prove that na ≤ nb.

We can start with our assumption that a ≤ b and calculate:

a ≤ b

na ≤ nb (since n ≥ 1)

na ≤ cnb (since c = 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-Oh 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⇒ loga n ∈ O(logb n)

We won’t ask you to expand the definition of Big-Oh, 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 logn 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.

Page 1/3

CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)

Solution

Proof. Let a, b ∈ R+. Assume that a > 1 and b > 1. Let n0 = 1, and let c = 1

logb a

.∗ Let n ∈ N, and assume

that n ≥ n0. We want to show that loga n ≤ c · logb n.

The logarithm change of base rule tells us the following:†

∀a, b, x ∈ R+, a 6= 1 ∧ b 6= 1⇒ loga x =

logb x

logb a

Using this rule, we can write:

loga n =

logb n

logb a

=

1

logb a

logb n

= 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 6= 1.

Page 2/3

CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)

3. Sum of functions. Now let’s look at one of the most important properties of Big-Oh: 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-Oh 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-Oh expanded), and use subscripts to help keep track of the variables.

Solution

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, if n ≥ n0 then g(n) ≤ cf(n). We want to prove that f + 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)

Page 3/3

学霸联盟