Question

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?

Answer 1

Answer:

O(n^2)

Explanation:

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)