Reference no: EM132108883

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

int f (n) {

 int sum = 0;

 for (i = 2; i < n; i = i * i)

   sum += i;

 return sum;

} // end f

Int sum = 0; // runs 1 time

for (i = 2; i < n; i = i * i) // runs log(n) times

sum += i; // runs 1 time for each value of the loop

For n = 10 the loop will execute 2 times, for n = 100 the loop will execute 6 times. Therefore, the total is 1 + log(n) + 1 which is log(n).