Sunday, June 01, 2014

[mskefoyf] Tuning the epsilon algorithm

Consider a tunable algorithm with running time:
T(n)=f(1/ε) * n^(c+ε)
where f(x) is a given monotonically increasing function and c is a given constant.

For a given problem size n, what value of ε minimizes running time?  What is the overall shape of the curve as a function of n?  It is the envelope of all possible ε.

No comments :