Question

What is the big-O performance estimate of the following function?

int f (n) {
int sum = 0;
for (i = 0; i < n; i = 7 * i)
sum += i;
return sum;
} // end f

Answer 1

Since the loop index variable i is initialized to 0, this function will result in infinite execution for all values of n>=0.

If instead the loop index variable is initialized to 1, Big O performance estimate of the code is O(log n) with logarithm base as 7.

Step-by-step explanation:

Given function:

int f (n) {

int sum = 0;

for (i = 0; i < n; i = 7 * i)

sum += i;

return sum;

} // end f

The complexity is determined by the for loop. Starting value of the index variable i is 0. At each iteration the value of the index variable i is multiplied by 7 (i=7*i). But multiplication by 7 still leaves the value of the index variable as 0. So loop condition i<n will fail for all n>=0 and the loop will continue indefinitely since the termination condition will never be achieved.

However if the loop index variable i is initialized to 1 instead, the loop will run O(log n) times with 7 as the base of the logarithm due to successive multiplication of index variable by 7 at each iteration.

Answer 2

The time complexity of the code is O(log₇n).

Step-by-step explanation:

The i is updated by 7*i.On each iteration i is multiplied by 7.So on finding the time complexity of the code given above it will come out to be log base 7.

When we divide the input by 2 the time complexity is log base 2.

So on dividing it by 7 we get the time complexity of log base 7.