Write the running time of each code fragment as the best pos

Write the running time of each code fragment as the best possible Big O function

Solution

In order to understand about the Big-oh time complexity for iterative functions, you need to calculate no. of times most inner loop is running as a function of input (n).

A.) It is already given that it is O(n).

B.) Values of k will go like:

1, 10, 20, ..999999*n which is asymptotically equal to O(n) as asymptotically we don\'t take any constants to represent growth of a function.

C.) Part C is absolutely correct.

D.) Your answer is correct but asymptotically it is equal to O(n). As we drop any constant we have.

E.) Values of k will go like:

1, (k+1), (2k+1),...n which will evaluate to O(n).

F.) In order to get time complexity, you need to examine the no. of times inner loop is executing and in this case it will be O(n^2).

G.) you have done it correctly.

H.) Loop will run O(n^(1/3)).

I) Outside loop for n^2 and inner loop run n times. therefore overall time complexity is O(n^3).

Hope it helps. Do give your response and please split questions in small parts so that one can answer them easily.