Ask 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

+5
Answers (2)
  1. 21 February, 17:45
    0
    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.
  2. 21 February, 17:50
    0
    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.
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers