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