# Question

How can we modify almost any algorithm to have a good best-case running time?

## Answer to relevant Questions

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)).Is the function ⌈lg n⌉! Polynomially bounded? Is the function ⌈lg lg n⌉! Polynomially bounded?Let A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, ...Show that in any sub tree of a max-heap, the root of the sub tree contains the largest value occurring anywhere in that sub tree.Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a ¬ b] in O (1) time. Your algorithm should use Θ ...Post your question

0