The testing effort growth

Just wondering how a proof for "Number of test cases grows exponentially" could look like...

Define a program to be a function from a set of input variables to a set of output variables,

P = Input x P|Output = I x O 
  = { (j_1,...,j_n) x (o_1,...,o_m) }
  = { (j_1,...,j_n,o_1,...,o_m) }.

Each component of Input is supposed to have at least 2 elements. (If not, the input variable will never change the image value, in other words, the program's behavior, and can therefore be eliminated. The case where an input value is determine to be defined or not, Input ≃ { 0, {0} }.)

Also, I need to restrict to the case where the dim(I) > 1 because if not each extra value to test adds exactly one test case (linear growth).

Define a feature to be a selection of a subset of input variables combined with their image, that is, it's a restriction of the program to a subset of the domain, F = P|J, J < I.

We take a test case to be the a random variable

T : Input x Ω -> Input x Output
T(i, ω) = (i, T_1(i, ω),..., T_m(i, ω)).

Each T_j is an expected output or simply expectation or post-condition.

A test passes if T_j(ω) = P(i)_j for all j, or fails otherwise, for a test execution ω.

A test case of a feature is then simply T|F = T|J x Ω where F = P|J.

For a given feature we can add new behavior minimally by

1. extending the domain of an input variable J_i by an additional value j' that defines a new behavior of the program, that is for some i, J_i' = J_i + { j' } and Input = J_1 x ... x J_i' x ... x J_n
2. extending the set of input variables by an additional dimension J_n+1

Both will result in an extended feature F'.

For 2. it is easy to see that

#T|F' = #{ (J_1,...,J_n) x J_n+1 x O } 
      = #J * #J_n+1 * # O 
      = #T|F * #J_n+1
      ≥ #T|F * 2.

As for 1., given that dim(J) > 1 each new value j' creates another full set of combinations of input variables (j_1,...,j',...,j_n), that is, the number of added test cases is

#T|F' - #T|F = #J_1,...,^J_i,...,J_n
                               ≥ 2^(n-1)

where ^J_i denotes not selecting this component.

Therefore,

#T|F' ≥ #T|F + 2^(n-1).

So, in general adding a new value to test, the lower bound for growth is 2^(n-1).  ⃞

Considering that the effort E|F of testing a feature depends on the selected test suite S|F < T|F, we might dare say that selecting S|F and the methods to evaluate T(i, ω) is a very important activity in testing.

I hope this makes sense...