I am working on an interesting algorithm: Its absolute error is exponential in a parameter $j \in \mathbb{N}$, and for a given $j$, I have complete freedom to choose between an $\mathcal{O}(1)$ time-complexity algorithm with memory consumption ${\sim}2^{j}$, or a $\mathcal{O}(2^j)$ time-complexity algorithm with $\mathcal{O}(1)$ memory consumption. I can also "meet in the middle" and consume any intermediate amount of memory and compute that I wish.

I'm having trouble deciding on how make the compute/memory/accuracy tradeoffs. Have there been cost functions developed that could help answer this question?

Obviously, I could write something like $$ \mathrm{cost} = c_1 t + c_2 m + c_3 e $$ for evaluation time $t$, memory consumption $m$ and error $e$, and just pick three positive constants $c_1, c_2, c_3$. But I would prefer to use a cost function that someone has already put some thought into.

  • $\begingroup$ If you can modify the behaviour with parameters (as opposed to being to reprogram the whole algorithm), this is a good time to employ an autotuner. Determining the best trade-off from purely theoretical concerns will almost certainly give suboptimal performance. $\endgroup$
    – Richard
    Mar 1, 2019 at 22:32
  • $\begingroup$ @Richard: Do you have a recommendation for an autotuner? $\endgroup$
    – user14717
    Mar 1, 2019 at 22:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.