Estimate (using O() notation) the number of additions and multiplications performed by the code below (as a function of n):
idx = 1
temp = 0
while ( idx < n )
temp = temp + idx
idx = 2(idx)
However, there is no answer to the problem and it is never mentioned again. I am wondering how i would go about this problem and how to come to a solution as it could still appear on the final exam for my course.
You need to count the number of times in the loop.
If the condition was removed then $\text{idx}_k = 2^k$.
The condition is satisfied as long as $2^k <n $ or $k = \lfloor \log_2 n \rfloor$, so since we have $k=0,...,\lfloor \log_2 n \rfloor$, the loop is entered $\lfloor \log_2 n \rfloor+1$ times.
Each time through there is one addition and one multiplication so the exact number is given by same formula.
In terms of $O$ notation, I would write $O(\log_2 n)$.