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

Question

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

score 2 · Accepted Answer · 2022-03-07 12:58:27Z

2

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

answered Mar 7, 2022 at 10:53

user16034

$\begingroup$ 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)$. $\endgroup$
– Tiamin
Mar 7, 2022 at 13:55
$\begingroup$ @Tiamin: can you substantiate ? [My claim is easy to check on small $n$.] $\endgroup$
– user16034
Mar 7, 2022 at 14:56
$\begingroup$ @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. $\endgroup$
– Russel
Mar 7, 2022 at 22:53
$\begingroup$ I see it now. Thanks guys. $\endgroup$
– Tiamin
Mar 7, 2022 at 23:27

Add a comment |

1 Answer 1