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

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.

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=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.

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

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.