6
$\begingroup$

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

enter image description here enter image description here

$\endgroup$
4
  • 2
    $\begingroup$ I did not check the details of your analysis, but what you did is called amortized analysis. Congratulations! (Avoid using the word "average"; that way lies the association with expected time resp. average-case, which is not what you do.) $\endgroup$
    – Raphael
    Mar 18, 2015 at 22:11
  • $\begingroup$ @Raphael I'll be honest, I'd always thought amortized analysis was average-case analysis. After a bit of searching, I see this is not the case. Thanks for clarifying! As for the term 'average', what might be a less misleading term in this context? I can see the problem, but what I'm calculating is the actual mean of something. $\endgroup$
    – concat
    Mar 18, 2015 at 22:29
  • 1
    $\begingroup$ If you sum up the (exact) costs of a sequence of $n$ operations, you get the total cost of this sequence. Dividing by $n$ is not meaningful per se (you don't get out a quantity that "actually exists"); we call the result the amortized cost of (each) single operation. So you can stick with that. If you want to emphasize that each operation get assigned the same share of the total cost, I think mean (as in sample mean) is probably safe to use. $\endgroup$
    – Raphael
    Mar 18, 2015 at 22:55
  • $\begingroup$ @Raphael Ah, that makes sense. I've edited to improve the terminology. Thanks! $\endgroup$
    – concat
    Mar 18, 2015 at 23:08

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Until the OP's edit about 30 minutes ago, I hadn't seen that algorithm, and so assumed s/he (and Wikipedia) were talking about the naive one consisting of just n calls to the usual update function. Indeed the now-linked algorithm is effectively the same as mine (but "pulls" instead of "pushes"). $\endgroup$ Jun 26, 2015 at 17:47
1
$\begingroup$

[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?)

$\endgroup$
3
  • $\begingroup$ Hmm... thanks for pointing out the graph inconsistencies, I'll check which is accurate. I notice now that in the question, I neglected to mention that I am not using the naive construction. The algorithm in question sums previously-calculated values, not raw values from the array. I didn't realize this wasn't the accepted method — I thought it seemed silly to do it the naive way. The construction algorithm $\endgroup$
    – concat
    Jun 26, 2015 at 17:03
  • $\begingroup$ Thanks for sharing your answer; your in-place algorithm is very interesting! I wonder if these two have the same efficiency? $\endgroup$
    – concat
    Jun 26, 2015 at 17:10
  • $\begingroup$ OK, if you're not using the naive algorithm then a lot of what I've said is wrong... I haven't seen the algorithm you linked to described anywhere else. I believe it's essentially the same as mine (as David Eisenstat said in a comment on the SO page) -- but yours "pulls" values while mine "pushes" :) $\endgroup$ Jun 26, 2015 at 17:55

Your Answer

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

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