This is a continuation of an earlier question on the trade off between time and query complexity. By a trade off we consider the following two types of algorithms:The best query algorithm: this algorithm uses the minimal number of queries and then optimizes to reduce total time, while preserving queries (this has query complexity $Q_1$ and time complexity $T_1$).The best time algorithm: this algorithm uses the minimal amount of time and then optimized to reduce total queries, while preserving time (this has query complexity $Q_2$ and time complexity $T_2$).We saw that for partial functions, we can have arbitrarily large seperations between $T_1$ and $T_2$ and $Q_1$ and $Q_2$. However, this approach only works for partial functions.For total functions, we can use the approach in this question to show that $T_1 \in O(n!2^n T_2)$ and for queries we can show $Q_2 \in O(2^{Q_1})$. Thus for total functions there seems to be a bound on the total separation. Can we improve it? Or come up with total functions with provable separations?(We have a potential candidate for a separation in this answer but no provable results)
Trade off between time and query complexity for total functions
cc.complexity theory;time complexity;query complexity