Tutorial 5, CPSC 331, Winter 2017

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  java -  references -  Mike Jacobson

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 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23 -  Tutorial 24

 Asymptotic Notation

About This Exercise

This exercise can be used by students to make sure that they understand the basic concepts concerning asymptotic notation that have been discussed in class.

Students should read through this exercise, and spend time trying to solve the problems on it, before attending the fifth tutorial.

Expected Background and Preparation

As noted above, the following problems test comprehentions and abilty to apply material presented during the lecture on asymptotic analysis.

A comprehensive discussion of this topic can be found in Chapter 3 of the textbook, Cormen, Leiserson, Rivest and Stein’s Introduction to Algorithms.

A set of additional set of worked examples of solutions of problems is now available as well. Students might find it to be useful to study these examples before attempting the longer problems at the end of this exercises.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lectures in which asymptotic notation has been discussed, and carefully read through the material about this topic that is now available.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions should contact the course instructor to get extra help.

  1. Give the definition of each of the following relationships between a pair of functions f and g. You may assume that each is a function of a single number n.

    1. f ∈ O(g)
    2. f ∈ Ω(g)
    3. f ∈ Θ(g)
    4. f ∈ o(g)
    5. f ∈ ω(g)

  2. Now say in your own words what each of things means about the relative rates of growth of the functions that are being compared.

  3. What is a “limit test?” There are two such test in the notes on asymptotica notation; what can they be used to prove?

  4. Use asymptotic notation to state relationships between each of the following pairs of functions on n. Try to use this notation to give as much information as you can.

    1. n and n2
    2. n and √n (that is, n0.5 )
    3. n2 and 2n
    4. 2n and 3n
    5. 0.001 n4 and 10000 n3
    6. 5 n2 and 3 n2 + 1000 n
    7. 1 and 1/n

Problems To Be Discussed in the Tutorial

The following more challenging problems will be discussed during the tutorial. Please try to solve them before you attend the tutorial, so that you can compare your solutions (if you got some) to the solutions presented by the teaching assistant, or so that you can better focus on the parts of the exercise that you found to be difficult, otherwise.

  1. Write proofs of each of the following claims about functions of a positive integer n.

    1. n2−n ∈ Ω(n2)
    2. n3 ∈ o(n4)

    See whether you are able to prove the second result both by using a limit test, and also without using one.

  2. Try to use asymptotic notation to simplify the analysis that you carried out when answering Question #8 of the previous tutorial exercise.

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W17/tutorials/tutorial5.html