2
$\begingroup$

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

1 Answer 1

3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.