Solution Manual

3.1-3 Explain why the statement, “The running time of algorithm A is at \[O(n^2)\]  ,” is meaningless. Solution: Let us assume the runn...

3.1-2 Show that for any real constants a and b , where $$b > 0 , (n + a)^b =\Theta(n^b)$$ Solution: To prove this, we have to show ...

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

2-4 Inversions 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...

2-3 Correctness of Horner’s rule The following code fragment implements Horner’s rule for evaluating a  polynomial $$ \begin {align} P(x...