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

Your indendation is a little off. If $f(i) \leq k$, is $i = 2i$ still executed? — Mees de Vries, Sep 27 '16 at 16:09
Sorry about that. I am assuming it is done in the while loop. The question was posed as if it were lined up with the if though. — MathIsHard, Sep 27 '16 at 16:13

score 1 · Answer 1 · answered Sep 27 '16 at 16:20

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

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

1 Answers1