School of Computer Science

Carleton University

Name: A.M. Problem Set: 1 Course: COMP 3804 Week: 1

Problems

Consult references [1, 2]. Problem 1. Show that 1 + 2 + 3 + ⋯ + n = \frac{n(n+1)}{2} Problem 2. Show that 1 + 2 + 3 + ⋯ + n ∈ O(n^{2}) Problem 3. Show that 1 + 2 + 3 + ⋯ + n ∈ Ω(n^{2}) Problem 4. Show that ∑_{k=1}^{n} k^{2} ∈ Θ(n^{3})

Problem 5. Show that \frac{1}{3}n^{2} − 3n ∈ O(n^{2}) Problem 6. Let p(n) = ∑_{i=0}^{d} a_{i}n^{i} be a polynomial of degree d and assume that a_{d} > 0. Show that p(n) ∈ O(n^{k}), where k ≥ d is a constant. What are c and n_{0} if we use the following definition of O-notation: O(g(n)) = {f(n) : ∃ c, n_{0} > 0 such that f(n) ≤ cg(n), ∀n ≥ n_{0}}. Problem 7. Let p(n) = ∑_{i=0}^{d} a_{i}n^{i} be a polynomial of degree d and assume that a_{d} > 0. For k ≥ d,

show that lim_{n→∞} ^{\frac{∑_{i=0}^{d} a_{i}n^{i}}{n^{k}}} = a_{d}n^{d−k} ≥ a_{d} > 0 and conclude that p(n) ∈ Ω(n^{k}).

Problem 8. Let p(n) = ∑_{i=0}^{d} a_{i}n^{i} be a polynomial of degree d and assume that a_{d} > 0. Show that p(n) ∈ Θ(n^{d}). (Hint: Using limits show that lim_{n→∞} \frac{p(n)}{n^{d}} = a_{d} and 0 < a_{d} < ∞. Thus, p(n) ∈ Θ(n^{d}). Recall that f(n) ∈ Θ(g(n)), if 0 < lim_{n→∞} \frac{f(n)}{g(n)} < ∞.) Problem 9. Show that 6n log n + \sqrt{n} log^{2} n = Θ(n log n). Problem 10. Fibonacci numbers are defined recursively as follows: F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for any integer n > 1. Using induction show that F_{n} ≥ 2^{\frac{n}{2}} for any n ≥ 6.

References

[1] S. DasGupta, C. Papadimitriou, V. Vazirani. Introduction to Algorithms. McGraw Hill.

[2] A.  Maheshwari.  Notes  on  Algorithm  Design,  Chapter  1,

    https://people.scs.carleton.ca/~maheshwa/Notes/DAA/notes.pdf