1
$\begingroup$

The original copy of the question on MSE.

Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows:

  • The root has label $S$,
  • for each node $x$ in the tree, and label $l$,

    • $x.left.l = x.l_0 + x.l_1$,
    • $x.right.l = x.l_0 - x.l_1$,

    where $l_0$ and $l_1$ are the first and second half of the sequence $l$.

For example, if $S=(1,2,3,4,5,6,7,8)$ we have the tree:

                 1, 2, 3, 4, 5, 6, 7, 8
                /                      \
    6, 8, 10, 12                       -4, -4, -4, -4
   /            \                      /             \ 
 16, 20       -4, -4                -8, -8,         0, 0
 /    \       /    \                /     \        /    \
36    -4    -8      0             -16      0      0      0

where the second level is obtain by

  • $(6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8)$,
  • $(-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7)$.

The problem is to compute the labels for the leaves. In the example, the labels for the leaves are: $36, -4, -8, 0, -16, 0, 0, 0$.

If I compute the tree recursively, the computational complexity will be $O(N \log N)$. That is a little slow for the purpose of the algorithm. Is it possible to calculate the labels for the leaves in linear time?

$\endgroup$
  • $\begingroup$ It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). $\endgroup$ – Kaveh Jun 9 '13 at 21:16
  • $\begingroup$ I edited your question, I think it should be easier to understand what you are looking for. I would suggest doing the same thing with the copy on Mathematics. For information about citing posts here in your paper please see How will you cite a discussion on this site in your paper?. You can also click on share and select cite to obtain automatically generated bibtex reference for the post. $\endgroup$ – Kaveh Jun 9 '13 at 21:36
  • $\begingroup$ @Kaveh: Alright, that sounds reasonable. I'm new here, so I did not know all the rules yet. This is fine for me. Thank you for the edits also! $\endgroup$ – researcher Jun 9 '13 at 21:42
  • 1
    $\begingroup$ An FYI to future people who stumble upon this: On the Math site, answerers noticed that the problem appears to reduce to the Hadamard transform, so it is unlikely that there is a $\mathcal{O}(N)$ solution. $\endgroup$ – apnorton Jun 10 '13 at 0:14