Chapter 4, Problem 12R

a)

Explanation of Solution

Running time of algorithm A:

Given:

Running time algorithm A is $O\left(f\left(n\right)\right)$

Reason:

• If the $cf(n)$

b)

Explanation of Solution

Worst case running time of algorithm A:

Given:

Worst case running time of algorithm A is $O\left(f\left(n\right)\right)$

Reason:

• The worst case running time is always greater than or equal to the average case running time