Given an n-element array X, algorithm D calls algorithm E on each element X[i]. Algorithm E runs in O(i) time when it is called on element X[i]. What is the worst-case running time of algorithm D?
The number of elements in the array X is proportional to the algorithm E runs time:
For one element (i=1) -> O(1)
For two elements (i=2) -> O(2)
.
.
.
For n elements (i=n) -> O(n)
If the array has n elements the algorithm D will call the algorithm E n times, so we have a maximum time of n times n, therefore the worst-case running time of D is O(n^2)
