Timeline for Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2024 at 22:51 | comment | added | David Eisenstat | @KennethKho Unfortunately the question was unclear, and these answers are discussing different algorithms. | |
| Mar 14, 2024 at 14:20 | comment | added | Kenneth Kho | The claim "tighter bound of $O(n)$ is also correct" requires proof, as the other answer points out that it is unlikely. | |
| Jun 26, 2015 at 17:49 | history | edited | David Eisenstat | CC BY-SA 3.0 | trivial edit to allow -1 to be backed out |
| Jun 26, 2015 at 17:47 | comment | added | j_random_hacker | 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"). | |
| Mar 18, 2015 at 18:53 | history | answered | David Eisenstat | CC BY-SA 3.0 |