Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '12 at 6:13
    
Included the image, but I agree that more explanation is needed. –  David Roberts Dec 4 '12 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 '12 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 '12 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 '12 at 13:35
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.