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

Question

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 are exactly $\lg(n)+\sum\limits_{j=0}^{\lg(n)-1} j2^{{\lg(n)-1}-j}$ operations to be performed over exactly $2^{\lg(n)}$ numbers, and the limit also approaches $1$. Testing seems to reveal that no other values of $n$ with the same $\lfloor \lg(n) \rfloor$ values have a higher mean number of operations per element than these.

If the amortized cost of inserting each element is indeed constant, shouldn't constructing the tree be $\Theta(n)$ time?

Testing:

I've tested the ranges between admittedly small consecutive powers of two, both by applying the summation and by brute force, and the results seem to agree:

Code using summation: http://pastebin.com/T3EEM7qz

Code using brute force: http://pastebin.com/sxdAkgxn

Answer 1

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

Answer 2

[EDIT: Everything down to the horizontal line was written under the assumption that the algorithm being used was the obvious naive one, in which we simply call update(i, A[i]) for every $1 \le i \le n$. But the OP had a cleverer algorithm in mind... which s/he has now actually described ;-)]

The main problem with your analysis is that the number of Fenwick tree operations (additions or writes to the array) required to update it with some value $i$ is not equal to the number of trailing zero bits in $i$. It's equal to the number of range sums that $i$ needs to be included in, which can all be found by repeatedly adding the least significant 1-bit present in $i$ to $i$ until it escapes past the maximum possible index, i.e., by using the update rule

void update(int idx ,int val){
    while (idx <= MaxVal){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

taken from this nice tutorial.

In the best case, which is when $n$ is 1 less than a power of 2, this works out to be $\lfloor \lg n \rfloor - y_i - f_i + 1$ operations, where $y_i$ is the total number of 1-bits in $i$, and $f_i$ is the number of trailing 0-bits in i. (Every non-trailing 0-bit position $0 \leq j \leq \lfloor \lg n \rfloor$ in $i$, including those $j$ for which $2^j > i$, is the position of the lowest 1-bit of exactly 1 index that $i$ contributes to, and each of them can be reached in constant time due to the magic of ripple carries.) The worst case occurs when $n$ is a power of 2: this adds exactly 1 more operation to every update over the best case. (The worst-case value of $i$ is of course $i = 1$.)

None of this rules out the possibility that the naive construction algorithm actually is O(n) -- but it seems very unlikely. Using code similar to yours I find that empirically, the mean number of operations required by the naive construction algorithm seems to increase logarithmically with $n$:

NEW WORST: 1.000000 for n=1
NEW WORST: 1.500000 for n=2
NEW WORST: 2.000000 for n=4
NEW WORST: 2.500000 for n=8
NEW WORST: 3.000000 for n=16
NEW WORST: 3.500000 for n=32
NEW WORST: 4.000000 for n=64
NEW WORST: 4.500000 for n=128
NEW WORST: 5.000000 for n=256
NEW WORST: 5.500000 for n=512
NEW WORST: 6.000000 for n=1024
NEW WORST: 6.500000 for n=2048
NEW WORST: 7.000000 for n=4096
NEW WORST: 7.500000 for n=8192
NEW WORST: 8.000000 for n=16384
NEW WORST: 8.500000 for n=32768

Finally, in case you're interested, I came up with a simple in-place algorithm for this that uses exactly 1 addition operation per array index in response to a similar question on SO.

---

P.S.: Since I actually went through your question before realising that the thing you were counting wasn't quite right, let me just detail a couple of small further problems with it:

To get an upper bound on the mean you need to pick a lower bound on n to go in the denominator of the limit, e.g.:

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

and in any case,

$\lim_{n\to\infty}{\sum\limits_{j=0}^n \frac {j}{2^{j}}} =2$,

not 1 as you claimed. (Obviously this wouldn't change the asymptotic complexity; also, although this constant appears to be loose from looking at your graphs, I find that it actually agrees with the numbers output by your brute-force code snippet, which hover just below 2 -- are the graphs "right", or the code?)