Question

Assume evaluating a function f(n) in the pseudocode below takes theta(n) time.
i = 1;
sum = 0;
while (i <= n)
do if (f(i) > k)
then sum += f(i);
i = 2*i;
What is the

Answer 1

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


i value is increased by a factor of 2 through each iteration
so, i values are 1, 2, 4, 8, ..., n/4, n/2, n
so, f(i) values are 1, 2, 4, 8, ..., n/4, n/2, n
so, total time complexity is 1 + 2 + 4 + 8 + ..., n/4 + n/2 + n
flip this expression
=>  n + n/2 + n/4 + ... + 1
=>  n(1 + 1/2 + 1/4 + 1/8 + ...)
we know that 1 + 1/2 + 1/4 + 1/8 + ... <= 2
so, n(1 + 1/2 + 1/4 + 1/8 + ...) <= 2n
hence time complexity is O(n)

Answer: O(n)