Chapter 4, Problem 32R

Explanation of Solution

Given:

It is given that in n-element array, the Algorithm D calls the Algorithm E on each element $X\left[i\right]$ and the algorithm E runs in $O\left(i\right)$ time.

Worst case running time:

The worst case running time measures the resource required in the algorithm. While calculating the running time it takes the input size of “n” to calculate the algorithm. This running time is referred as worst case running time.

• Since, the algorithm E depends on the “i” value and it executes in O(i) time then it is linearly proportional to i.

${\displaystyle \sum _{i=1}^{n}i}$

From the above expression, the time complexity of algorithm E for each value of $X\left[i\right]$ is

$$