3 ms·
I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear
by shawntan 3y ago
I guess I should say the recurrence growing as a function of the input size is something people don't seem to be willing to afford, not specifically the linear dependence.
Not to mention parity here is a toy problem to highlight the issue, but there can be other problems that require recurrence linear or quadratic in the size of the input.
- yarg 3y agoSure, but a toy problem that's substitutable for many other functions. In this case you could substitute the XOR function for any other merge function. As far as the variable depth is concerned, utilisation is an issue that introduces additional complexity, but otherwise I don't see the problem. (No one's expecting fixed compute time for differently sized data elements.) You can get around that one by building a log(n) threaded pipeline for your log(n) depth network (something like this: https://imgur.com/a/xL4rhFu https://imgur.com/a/xL4rhFu).