Determine what is the best order for running filters on a dataset I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.

Each task filters a percentage of the dataset.

Assuming I got the tasks t1, t2, t3, ..., ti and a dataset. Each task have an execution time per item in the dataset denoted as e1, e2, e3, ..., ei and each task filters a certain percentage of the dataset denoted as f1, f2, f3, ..., fi. 

What is the optimal sequence of tasks to achieve the minimum running time ?

I've first tried to examine two tasks - t1 and t2 with their representative execution time and filter percentage - e1, f1 and e2, f2.

I want to find the ordering predicate for getting e1 + f1*e2 &lt; e2 + f2*e1. I'll get the condition e1 / (1 - f1) &lt; e2 / (1 - f2). And I guess that from here I'll need to prove it in induction, but I'm stuck because the equation is some kind of recursion.
You can prove that the optimal ordering is according to ascending order of e(i)/f(i).

Proof:

Let r(i) = 1 - f(i).
The total cost of an ordering is: e(1) + e(2)*r(1) + e(3)*r(2)*r(1) + ... + e(N)*r(N-1)*...*r(1)

Now, assume that there's an optimal ordering that doesn't follow the rule above. It follows that there are two adjacent tasks t(i) and t(i+1) such that e(i)/(1-r(i)) &gt; e(i+1)/(1-r(i+1)) =&gt; e(i)*(1-r(i+1)) &gt; e(i+1)*(1-r(i))
swapping these two will change the value of only two expressions in the total cost expression, resulting in a delta of:

e(i) * r(i-1)*...*r(1) + e(i+1)*r(i)*...*r(1) -
e(i+1)*r(i-1)*...*r(1) + e(i)*r(i+1)*r(i-1)*...*r(1) =
r(i-1)*...*r(1)*[e(i) + e(i+1)*r(i) - e(i+1) - e(i)*r(i+1)] =
r(i-1)*...*r(1)*[e(i)*(1-r(i+1)) - e(i+1)*(1-r(i))] &gt; 0


The delta is positive, meaning that the original configuration is more expensive than the outcome of the swap, therefore we have a contradiction.