We are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Consider the following recurrence relation:
We are interested in calculating $$$f(n)$$$. Is there a way to calculate it with the time complexity being better than $$$\mathcal{O}(n^2)$$$?
UPD: I forgot to mention that the array $$$b$$$ is increasing (i.e. $$$b[i] \leq b[i+1]$$$). Don't know if that helps though...