Let N be the number of true parameters at the start of execution. [This defaults to size (all true), but the user can edit them.]
If N = 0, the program will never go through a loop, so end time = 0, regardless of initialization mode. Therefore, when considering the behavior of the following initialization modes, assume N > 0.
Since Dependencies[index,dep] is false for every index and dep, no NewParameters[dep] ever has a chance of being set to true. When Parameters[] is overwritten with NewParameters[], it is set to all false, and so the execution terminates after one time through the loop.
Each parameter is dependent only upon itself, so every turn, each true parameter has a 50% chance of going false. Once it goes false, a parameter will never go true again, because it depends upon itself. At time 0, there are N true parameters. At time 1, there are on average N/2 true parameters. At time 2, there are N/4, etc. So, the end time is on average log2 N + 1.
Consider the case where N=4 and Size >= 4. For simplicity, at the start of execution, assume we "shift left" each of the true parameters to fill the spots left by the false parameters. We get the same result (time wise) in the end. The following table describes the chances of a given parameter being true the following turn:
CURRENT # true chance of being STATE depends true next turn param 1 2 3 4 1 2 3 4 1 2 3 4 ------- ------- ------------------- 1 1 1 1 1 2 3 4 1/2 3/4 7/8 15/16 1 1 1 0 1 2 3 3 1/2 3/4 7/8 7/8 1 1 0 1 1 2 2 3 1/2 3/4 3/4 7/8 1 1 0 0 1 2 2 2 1/2 3/4 3/4 3/4 1 0 1 1 1 1 2 3 1/2 1/2 3/4 7/8 1 0 1 0 1 1 2 2 1/2 1/2 3/4 3/4 1 0 0 1 1 1 1 2 1/2 1/2 1/2 3/4 1 0 0 0 1 1 1 1 1/2 1/2 1/2 1/2 0 1 1 1 0 1 2 3 0 1/2 3/4 7/8 0 1 1 0 0 1 2 2 0 1/2 3/4 3/4 0 1 0 1 0 1 1 2 0 1/2 1/2 3/4 0 1 0 0 0 1 1 1 0 1/2 1/2 1/2 0 0 1 1 0 0 1 2 0 0 1/2 3/4 0 0 1 0 0 0 1 1 0 0 1/2 1/2 0 0 0 1 0 0 0 1 0 0 0 1/2 0 0 0 0 0 0 0 0 0 0 0 0
At time 0, N parameters are true. At time 1, (1/2 + 3/4 + 7/8 + 15/16 = (8+12+14+15)/16 = 49/16) roughly 3 parameters are true. After that, the math gets complicated.
A way of approximating is to consider only the leftmost true parameter, that is, the parameter with the fewest true dependencies (only itself) and therefore the greatest chance of turning false. Once it turns false, it can't come back to true, so the role of leftmost parameter passes to the next parameter.
Since in a given turn, there's a 1/2 chance that the leftmost true parameter will fail, on average, it will take 2 turns for the leftmost parameter to fail. In the turn it fails, there's an additional 1/4 chance that the next leftmost also fails, and a 1/8 chance that the next leftmost also fails, and so on.
Therefore, the average expected "lifespan" of a given parameter is a little less than 2N, where N is the number of initially true parameters.
Each true parameter depends upon all of the other parameters. Therefore, if in a given turn, M parameters are currently true, then the chance of a parameter being false next turn is roughly 1/M2.
A parameter goes false "for good" when all its dependees are false. The chance of all its dependees being false is (1/M2)M = 1/M2M
When a parameter goes false for good, not only it, but ALL of the co-dependent parameters go false for good (i.e., the entire set of parameters, since they are all co-dependent).
Therefore, the entire set will go false for good in roughly N2N turns. It's actually a little less than that, because each turn has a 1/M2M chance of complete failure, and M <= N.
Assume block size = 1, and that the pattern is aligned on the diagonal (i.e. in a 3x3 matrix, the following are true: [1,1], [1,3], [2,2], [3,1], [3,3]). This is the pattern my program uses.
Regardless of block size, the parameters form two subsets of co-dependent parameters. (The subsets themselves are independent). Therefore, if in a given turn, M parameters are currently true, then the chance of a true parameter being false next turn is roughly 1/(M/2)2.
The expected time to failure for a given subset is roughly (M/2)2*M/2 = (M/2)M turns, so we can expect both parameter subsets to have failed by (roughly) turn 2(N/2)N (actually a little earlier, for the same reason I mentioned in part d).
This is just a guess! I wonder how you'd calculate this mathematically...
I verified all of these by testing them. I didn't wait for cases d and e to go all the way through for large sizes.
Since size can go up to 24, there can be up to 24 * 24 = 28 = 256 elements in Dependencies[][]. Each element can be true or false, so there are 2256 possible settings for the Dependencies[][] array.
There are also 24 = 16 elements in Parameters[], any of which can be set to true or false. So there are 216 different initial settings for Parameters[].
In all, for size=24=16, there are (2256 * 216 = 2272) possible input settings. This is just for size=16. We must also consider sizes of 15, 14, etc. on down to size = 1.
In general, there are 2size(size + 1) input combinations. So, in all, there are SUM16i=12i(i+1) input combinations = 2272 + 2210 + ... + 22 = still only a little more than 2272.
2272 = (210)27.2 = roughly (103)27.2 = roughly 1082
You can probably take short cuts by assigning equivalence classes. For instance, consider the cases where N = 2:
CLASS A CLASS B CLASS C ------- ---------- ---------- etc. 1 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0However, for a thorough, brute-force black-box testing (which I think is the purest and most convincing form of testing), you wouldn't be allowed to take any shortcuts.
If size can go up to 216 = 65536, then there will be a little more than 265536*65537 = 24295032832 test cases. This is roughly (103)429503283.2 = 101288509850 test cases.
The total testing time is therefore around 101288509850 * 3.1688 * 10-26 AU = 3.1688 * 101288509850-26 = around 101288509824 AU.