Consider

$$$R_k = \sum_{j = 0}^{ j = k - 1} \sqrt\nu_j(\sqrt{k - j} - \sqrt{k - 1 - j})$$$ $$$\newline$$$ Can we compute $$$\sum_{j = 1}^{j = K} \nu_kR_k$$$ in less than O(K^2) ? $$$\newline$$$ $$$\nu$$$ and $$$R$$$ are arrays of double of size $$$K$$$ $$$\newline$$$ The answer is a double.

Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Auto comment: topic has been updated by chika10 (previous revision, new revision, compare).Is there a reason behind this particular expression? Or was it just random.

It's from mathematical finance.

The vector $$$R$$$ is called the response function and the vector $$$\nu$$$ is the trading strategy.

$$$R$$$ is just a convolution of two polynomials.

First is $$$A[X] = \sum_{j=0}^{k-1} \sqrt{\nu_j} X^j$$$.

Second is $$$B[X] = \sum_{j=0}^{k-1} (\sqrt{j + 1} - \sqrt{j}) X^j$$$.

use FFT to compute $$$R$$$ in $$$O(K \log K)$$$, and then you can compute the sum that you require.

Wow! Thank you!!