# Time complexity of an algorithm in the $\Theta$ notation

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

The total number of inner loop tests is the sum of the number of trailing zeroes in the numbers from $$1$$ to $$n$$.

If $$n=2^m$$, every other number is even, every fourth number is a multiple of four and so on. Hence

$$T(n)=n+\frac n2+\frac n4+\frac n8+\cdots 1=2^{m+1}-1=2n-1.$$

When $$n$$ lies between two powers of $$2$$, $$T(n)$$ is intermediate as well.

$$T(n)=\Theta(n)$$

• Hi, I'm not sure if I understand the second paragraph. If in the first sentence of the answer you're talking about the sum of trailing zeroes in the binary representation of numbers, I would agree with that, but I think this sum would be more complex than your $T(n)$. Mar 7, 2022 at 13:55
• @Tiamin: can you substantiate ? [My claim is easy to check on small $n$.]
– user16034
Mar 7, 2022 at 14:56
• @Tiamin I think you can see it better if you imagine your process this way, initially you have a list $l$ of numbers from 1 to $n$. Then you divide each element in $l$ by 2 and remove from $l$ all odd numbers while replacing all even numbers by their quotient. You repeat this until $l$ is empty. So initially you have $n$, elements, then next iteration you'll have $n/2$, then $n/4$, and so on. Hopefully this helps, this is how i knew my answer earlier is wrong. Mar 7, 2022 at 22:53
• I see it now. Thanks guys. Mar 7, 2022 at 23:27