Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition:

Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst case $O(\lg n)$. The number of elements accessed from $F[0:k]$ to calculate $F[k+1]$ is equal to the number of trailing zeroes in $(k+1)_2$ which is at most $\lfloor \lg(n) \rfloor$. There are $n$ elements, so this is $O(n\lg n)$. Wikipedia seems to agree as well.

Thoughts:

NOTE: I am using this algorithm.

Consider the number of positive integers less than or equal to $n$ with exactly $j$ trailing zeroes in their binary representation, $j<{\lfloor \lg(n) \rfloor}$. Since the leftmost ${\lfloor \lg(n) \rfloor}-(j+1)$ digits can be freely assigned so long as the resulting number is less than $n$ ($j+1$ because the $(j+1)th$ digit from the right must be a $1$), there are between $2^{\lfloor \lg(n) \rfloor-j-1}$ and $2^{\lfloor \lg(n) \rfloor-j)}$ such numbers for any $n$.

Let an operation be defined as the summation of two numbers, which is assumed to be a constant time operation. (The other operations, like insertion, are also in constant time and are performed a constant number of times, hence they are ignored) Thus, for $j$ trailing zeroes, $j$ operations must be performed.

As a result, the total number of operations to perform is at most $\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}$. It must also be true that $2^{\lfloor \lg(n) \rfloor}≤n<2^{\lfloor \lg(n) \rfloor + 1}$. Note that both maxima occur when $n_2$ is filled with ones. If we take this case, the mean number of operations for any $j$ as $n \rightarrow \infty$ should be:

$\lim_{n\to\infty}\frac{\sum\limits_{j=0}^{\lfloor \lg(n) \rfloor} j2^{{\lfloor \lg(n) \rfloor}-j}}{2^{\lfloor \lg(n) \rfloor +1}-1}
=\lim_{n\to\infty}{\sum\limits_{j=0}^n \frac {j}{2^{j}}}
=1$

Now, if we take the other extreme, where $\lg(n)\in\mathbb{Z}$ ($n_2$ is a one trailed exclusively by zeroes) then there

Technically it is $O(n\log n)$, since big-O is an upper bound only, but your tighter bound of $O(n)$ is also correct. (Without loss of generality, it suffices to restrict $n$ to powers of two; then the proof is easy.)

StackExchange Computer Science Q#40540, answer score: 2