Consider the following algorithm:
res := 0
for i := 1 to n do
j := i
while j mod 2 = 0 do
j := j / 2
res := res + j
What's its time complexity in terms of the $\Theta$ notation?
What I have so far:
- The complexity is $\Omega(n)$ and $O(n\log n)$, but I'm having trouble finding a tight bound (according to the $\Theta$ definition I would have to find a function $f$ such that the function describing the cost of the algorithm is $\Omega(f)$ and $O(f)$).
- The cost of the inner loop in the $i$-th iteration is $T(i)=\begin{cases} O(1)&i\ \text{is odd}\\ O(1)+T(i/2)&i\ \text{is even}\\ \end{cases}$