# Question

Let f (n) and g (n) be asymptotically nonnegative functions. Using the basic definition of Θ- notation, prove that max (f (n), g (n)) = Θ (f (n) + g (n)).

## Answer to relevant Questions

Show that for any real constants a and b, where b > 0, (3.2) (n + a)b = Θ (nb).Argue that the solution to the recurrence T (n) = T (n/3) + T (2n/3) + cn, where c is a constant, is Ω(n lg n) by appealing to a recursion tree.Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray ...Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n). (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the ...You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence ...Post your question

0