Asymptotic Notation (Jan 30)

These links are all on the course website's schedule.

Warmup Exercises

Q1 and 2 test your knowledge of the five definitions: f∈O(g), f∈Ω(g), f∈Θ(g), f∈o(g), f∈ω(g). MAKE SURE YOU KNOW THESE. Yes I used caps.

Q3 is about the limit tests you can find in the lecture slides. (Page 32, slide 18/20). If you understand what's going on in the lecture slides, it should be easy to write out these limits in the future.

Q4 asks you to use the definitions in Q1 and Q2 to relate the given functions, and you should definitely do these. It'll take a couple minutes only.

Tutorial Exercise

Q5 a) and b) ask you to prove two claims. You should always state the definition first. This is why you had to practice defining the five asymptotic notations in warmup Q1. Next, you want to take the inequality/relation and manipulate/simplify it, to get some relation between constant c > 0 and n ≥ 0.

For Q5a), you are dealing with Big-Omega notation. Recall that when proving Big-Oh or Big-Omega, you only have to identify one pair of constants c and N₀ such that the inequality/relation holds. If you can express n in terms of c, then you should be able to pick your constants c and N₀. As covered in the lectures, the specific values of the constants mean very little in asymptotic notation, since we only care about the growth rates. Just make sure your constant c and all n ≥ N₀ satisfy the relation.

For Q5b), you are dealing with Little-Oh notation. Recall that when proving Little-Oh or Little-Omega, you have to show that for every constant c, there is some N₀ such that for all n ≥ N₀, the relation holds. Assuming you already manipulated the relation to express n in terms of c, you can then state exactly that. For example, if n > (1/c), then you can say that for every constant c, n > (1/c). Simple as that.

Q6 refers to the proof we did in Q8 of last tutorial. We determined the worst-case upper-bound to be 2n² + 3n - 2. This is in O(n²), as you should be able to prove now. To see how we can simplify our proof from last time using asymptotic notation, you can refer to the lecture supplement provided by the prof. Specifically, you want to look at example 3. As the supplement mentions, using this method for our algorithm results in a lower-bound of O(n). This is not what we want, because the lower bound is also 2n² + 3n - 2, which is in O(n²). If we used the linear bound of O(n), we actually have a very loose bound, which does not help us accurately describe the worst-case running time of our algorithm.

[T05Proofs.pdf][163KB]

Splitting the Sum

In the lecture supplement, a technique called Splitting the Sum is mentioned. It is not covered in this class, since it's taught in CPSC 413. The prof has allocated 5 bonus marks for question 3, if you use this approach. I do not recommend spending a tremendous amount of time on this. If you are interested, the technique is detailed on page 1152 of the CLRS (Introduction to Algorithms) Textbook, 3ed.