Reference no: EM132264304

Question 1:

In the following, let f and g be positive increasing functions. Answer each question and briefly justify your answers. You get no points if you do not give a justification.

(a) Given that f (n) = O(g (n)), is it possible that f (n) = Θ(g (n))? Is it always true that f (n) = Θ(g(n))?
(b) Given that f (n) = ω(g (n)), is it possible that f (n) = Ω(g(n))? Is it always true that f (n) = Ω(g (n))?
(c) Given that f (n) = O(g (n)), is it possible that f (n) = o(g(n))? Is it always true that f (n) = o(g (n))?
(d) Is it possible that f (n) = ω(g(n)) and also f (n) = 0 (g (n))?
(e) Is it possible that f (n) + g(n) = 0(min( f (n), g(n)))? Is it always true that f (n) + g(n) = O(min( f (n), g(n)))?

Question 2.
Give two asymptotically different functions, each of which belongs to both ω(n) and o(n²) . Briefly justify your answers.

Question 3.
Problem 3-2 of the Textbook (p.61), (c) - (f). Note that "A is O of B" means A = O(B), and similarly for other notations (o, Ω, ω, Θ). In your write up, copy and fill up the table with "Yes" or "No" in each table entry; after the table, briefly justify your answer for each sub-question. You get no points if you do not give a justification.
(Note: 5 points for each of (c) - (f).)

Question 4.

Let S₁(n) = Σⁿ_k=1 k, S₂(n) = Σⁿ_k=1k² and S₃(n) = Σⁿ_k=1 k³. In class, we already showed how to calculate S₁(n) and S₂(n). Your task here is to apply similar methods for S₃(n) .

(a) Without calculating the closed form, use rough estimations to derive a lower bound and an upper bound for S₃(n), so that you can use them to express S₃(n) in the Θ() notation. Give this Θ() notation in the simplest form (e.g., Θ() is in the simplest form but Θ(2n)) is not).

(b) Use the perturbation method (as discussed in class) to derive the closed form for S₃ (n). (Background Information: You would need the formula of S₁(n) and S₂ (n), which we already know: S₁(n) = n(n + 1)/2 and S₂(n) = n(n + 1)(2n + 1)/6.)

Question 5.

Given a sequence of n unordered real numbers, design and analyze an algorithm that finds both the smallest and the second smallest numbers among them using at most 3 [n/2] comparisons. Your algorithm should describe what to do when n is even and when n is odd. You need to show that your algorithm gives the correct answers, and that it uses at most 3 [n/ 2] comparisons.