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$

closed as not constructive by Kaveh Jun 9 '13 at 21:16

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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