Welcome to MathOverflow

Question

0

Hi, I wonder if there is 'an operation' that allow me to compute this special function faster than square-time $O(n^2)$.

Assume we have functions $f(x)$ and $h(x)$. $h(x)$ has a special point (maximum) which we are moving through the $f(x)$ and compute maximum. It's a little hard to explain so here is a photo:

My function that I want is this green one after finish process described above.

edited Dec 4 at 6:52

David Roberts
11.7k●2●18●55

asked Dec 4 at 5:55

ithinkso
11

Unfortunately the question is not clear at all. I would like to understand the kind of construction you have, and then why it takes you $O(n^2)$ to compute. Before that, I think it will be difficult for people to help... – Rodrigo A. Pérez Dec 4 at 6:13

Included the image, but I agree that more explanation is needed. – David Roberts Dec 4 at 6:52

Ok, maybe different approach: Let f(x) be our main function where 0 \leq x \leq n and another function is h(x) where 0 \leq x \leq m with one maximum h(b) (ofc 0 \leq b \leq m). I need to compute the following: G(x)=\max(f(x),\max{_{0\leq k\leq m}} \{h(k)+f(x+b-k)\}) for every x. But i think this is even less clear. I have problem with explaining it coz of my bad english. Try to imagine you have h function with one maximum at b, now for every x you have to move h by some vector to match h(b)=f(x) and compute maximum of this two functions. – ithinkso Dec 4 at 7:24

Ok, maybe different approach: Let $f(x)$ be our main function where $0 \leq x \leq n$ and another function is $h(x)$ where $0 \leq x \leq m$ with one maximum $h(b)$ (ofc $0 \leq b \leq m$). I need to compute the following: $G(x)=\max(f(x),\max{_{0\leq k\leq m}} \{h(k)+f(x+b-k)\})$ for every x. But i think this is even less clear. I have problem with explaining it coz of my bad english. Try to imagine you have h function with one maximum at b, now for every x you have to move h by some vector to match $h(b)=f(x)$ and compute maximum of this two functions. – ithinkso Dec 4 at 7:27

1

ithinkso: rather than leaving comments, it's better to edit your question. There's an "edit" link. – Tom Leinster Dec 4 at 13:35

show 1 more comment

Unusual function computation in signal processing

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.