Big O and running time of specific method given $\Theta(n)$ information on inner function

Question

If evaluating $f(n)$ is $\Theta(n)$

i = 1;
sum = 0;
while (i <= n)
       do if (f(i) > k)
            then sum += f(i);
          i = 2*i;

Would the running time of this be $O(nlogn)$ because i is doubled after each iteration and the function is called the same number of times? Or could it even be a linear case? I am very lost on this...

Answer 1

The worst case is if $f(i) \gt k$ is always true, so you can delete that from the code except that you compute $f(i)$ twice per loop. You are correct that you do $\log_2 n$ passes through the loop, so you do $2 \log_2 n$ evaluations of $f$. The final result is $f(1)+f(2)+f(4)+f(8)+\ldots f(2^k)$ for $k$ the smallest value where $2^k \gt n$ The sum of the arguments is about $2^{k+1} \approx 2n$ and the total time is about $4n$. The point is that the early passes are called with small values of the argument, so presumably they run faster than $\Theta(n)$