Tutorial 5, CPSC 331, Fall 2008

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16

Asymptotic Analysis and Standard Functions

About This Exercise

This exercise is based on material presented during the lecture on Monday, September 22.

The objectives of this exercise are

• to ensure that you understand asymptotic notation and its use to describe the worst-case running times of algorithms, and

• to ensure that you understand the definition and properties of “standard” functions that are frequently used to state bounds on running times.

Please read through and try to solve the problems on this exercise before attending the tutorial on Monday, September 29.

Note: Several of the following problems are taken from Chapter 3 of Cormen, Leiserson, Rivest and Stein’s text, Introduction to Algorithms, Second Edition. This is an excellent reference for this topic.

Problems To Be Solved

1. Use asymptotic notation to state bounds on the worst-case running times for the “Bubble Sort” and the “gcd” algorithms that were considered in the previous tutorial exercise.

   Of course your statements should be correct. They should also be as precise as they can be (using the notation that has been defined, and they should not be more complicated than necessary.

2. During the lecture on this topic, graphs were presented to provide evidence of each of the following relationships.

   1. 4x² + 2 ∈ O(x²)
   2. x² ∈ Ω(4x²+2)
   3. 4x²+2 ∈ Θ(x²)
   4. x ∈ o(x²)
   5. x ∈ ω(x^1/2).

   Use the formal definitions presented in class to sketch proofs of each of the above relationships.

   Then try to use a limit test to prove the relationships as well, whenever an appropriate “limit test” is available.

3. Write proofs of each of the following (without using limit tests).

   1. 2x³ + 4 ∈ Θ(x³)
   2. 2x³ + 4 ∉ O(x²)
   3. 2 x² ∉ ω(x²)

4. Let

   p(n) = a_d n^d + a_d−1 n^d−1 + … + a₁ n + a₀,

   where a_d > 0, be a polynomial with degree d in n, and let k be a constant. Use the definitions of the asymptotic notations given in lectures to prove each of the following properties.

   1. If k ≥ d then p(n) ∈ O(n^k).
   2. If k ≤ d then p(n) ∈ Ω(n^k).
   3. If k = d then p(n) ∈ Θ(n^k).
   4. If k > d then p(n) ∈ o(n^k).
   5. If k < d then p(n) ∈ ω(n^k).

5. Use asymptotic notation to state a relationship between each of the following functions f(n) and g(n), or say that none exists. You may assume that k ≥ 1, ε > 0, and c > 1 are constants.

   1. f(n) = (log n)^k and g(n) = n^ε
   2. f(n) = n^k and g(n) = cⁿ
   3. f(n) = √n (that is, the square root of n) and g(n) = n^sin n
   4. f(n) = 2ⁿ and g(n) = 2^n/2
   5. f(n) = n^log c and g(n) = c^log n

6. Let f(n) and g(n) be functions from the set of positive real numbers to the set of positive real numbers. Say whether each of the following claims is true or false. Then try to prove your answer.

   1. If f(n) ∈ Θ(g(n)) then g(n) ∈ Θ(f(n)).
   2. f(n) + g(n) ∈ Θ(min(f(n), g(n))).
   3. If f(n) and g(n) are functions such that f(n) ≥ 1 and log(g(n)) ≥ 1 for sufficiently large n, and f(n) ∈ O(g(n)), then log(f(n)) ∈ O(log(g(n))) as well.
   4. If f(n) ∈ O(g(n)) then 2^f(n) ∈ O(2^g(n)).
   5. f(n) ∈ O((f(n))²) for every function f(n).
   6. If f(n) ∈ O(g(n)) then g(n) ∈ Ω(f(n)).
   7. f(n) ∈ Θ(f(n/2)) for every function f(n).

---

This page last modified: http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial5.html