Next: Summary Results from the
Up: Supporting Theorems
Previous: An Example of Cyclical
In this section, a family of theorems are presented that pertain to the WaterSluice software engineering methodology.
The WaterSluice software engineering methodology will find solutions in static environments and dynamic environments including dynamic environments that
have the nonmonotonic property. If a solution exists and the
WaterSluice software engineering methodology finds the solution, the best case performance is O(1), the
worst case performance is O(N), while the
average case performance is an orderofmagnitude less than N where N is the total number of steps in the environment.
Theorem 4 (WaterSluice: Static Complete)
The WaterSluice software engineering methodology is static complete.
Let
be the n_{a} steps
leading to the possible analysis A with a_{1} being the
initial problem statement.
Let
be the n_{d} steps
leading to the possible design D.
Let
be the n_{i} steps leading
to the possible implementation I.
Let
be the n_{t} steps leading
to the possible testing T
with t_{n<<1931>>4} being the
final system acceptance
test.
Define an environment that consists of the four planes of analysis, design, implementation, and testing with each lower plane being a refinement of the higher planes.
In this environment priorities are represented
as different in the size of a step. A larger circle represents a higher priority than a smaller circle.
Define the solution as the tree, or in a more general sense,
the directed acyclic graph, of all steps from all four planes
used in the final system.
Define a priority queue of possible next steps PQ. Initially the
priority queue PQ contains the initial step a_{1}
represented by the sequence S^{1}.
Define a function, next, over all possible steps,
which generates all possible next steps given the current solution sequence,
evaluates the total value, and pushes the ordered result onto the priority queue PQ. Only high priority steps are
keep in the queue PQ.
See Figure 5.13 on page for a visual representation of the space.
Here a larger circle represents a higher priority step.
See figures 5.13,
5.15,
5.16,
5.17, and
5.18
on pages through
for a visual guide of the reasoning.
The numbers associated with the steps represent the order
visited by the methodology.
Figure 5.13:
Priority Based Space

Figure 5.14:
WaterSluice: Proof of Principle

Figure 5.15:
WaterSluice: Prototype

Figure 5.16:
WaterSluice: Alpha

Figure 5.17:
WaterSluice: Beta

Figure 5.18:
WaterSluice: Product

Proof 4.1
The WaterSluice methodology leads to this sequence
of steps.
 step 1: Initial set up.
PQ & = & a_{1}
 step 2: Remove a_{1} from the priority queue PQ. Expand all alternative steps near a_{1} using
the function next and push them onto the priority queue PQ.
At this stage there are two alternative next steps. Pick the
next step with the highest priority.
For clarity, assume this step is
a_{2}.
 step 3:

 step 11:
The methodology is now at the proof of principle stage.

 step 15:
The methodology is now at the prototype stage.

 step 24:
The methodology is now at the alpha stage.

 step 32:
The methodology is now at the beta stage.

 step
n_{a} + n_{d} + n_{i} + n_{t}:
The priority queue contains the last step of the final system acceptance test.
Thus, the WaterSluice software engineering methodology is static complete.
The WaterSluice software engineering methodology uses priority to guide the process combined with the iterative mechanism found in a cyclical methodology and governed by the steady progression found in a sequential methodology.
If the environment is static, then all steps in the environment are known before the WaterSluice software engineering methodology begins.
The WaterSluice software engineering methodology first discovers high priority steps from the analysis plane, the design plane, the implementation plane, and the testing plane.
As higher priority steps are discovered and visited, they
are eventually exhausted. This allows the lower
priority steps to be visited.
The WaterSluice software engineering methodology
continues until the only remaining step to visit is the lowest possible priority step.
Corollary 4.1 (WaterSluice: Dynamic Complete)
The WaterSluice software engineering methodology is dynamic complete.
Proof 4.1.1
The WaterSluice software engineering methodology allows for the introduction of new information at every step and the removal of information that is no longer needed.
Recall the presence of the priority queue. When steps are placed on the priority queue, the queue is rearranged. Low priority steps migrate to the end of the queue while high priority steps migrate to the beginning of the queue.
Regardless of when a high priority item
is discovered, the methodology will be able to react.
For a dynamic environment, the WaterSluice software engineering methodology will eventually find the solution.
Corollary 4.2 (WaterSluice: Nonmonotonic Complete)
The WaterSluice software engineering methodology is nonmonotonic complete.
Proof 4.2.1
The WaterSluice software engineering methodology allows for the introduction of new information at every step and the removal of information that is no longer needed.
Define a priority function that takes into account nonmonotonic steps. Consistent steps are assigned similar high priority. Nonconsistent steps are assigned lower priority.
When steps are placed on the priority queue, the queue is rearranged. Low priority steps migrate to the end of the queue while high priority steps migrate to the beginning of the queue.
Regardless of when a high priority item
is discovered, the methodology will be able to react.
For a nonmonotonic space, the WaterSluice software engineering methodology will eventually find the solution leaving behind the conflicting steps.
Corollary 4.3 (WaterSluice: Best Case)
The best case performance of the WaterSluice software engineering methodology is O(1).
Proof 4.3.1
Let the environment consist of
n_{a} analysis steps, n_{d} design steps, n_{i} implementation steps, and n_{t} testing steps.
Let the correct analysis step be the very first step
a_{1}.
Let the correct design step be the very first step
d_{1}.
Let the correct implementation step be the very first step
i_{1}.
Let the system acceptance test be the very first step t_{1}.
To satisfy the problem statement would
require one analysis, one design, one implementation, and one testing step.
In this environment the WaterSluice software engineering methodology will require only four steps. Thus the performance is O(1).
Corollary 4.4 (WaterSluice: Worst Case)
The worst case performance of the WaterSluice software engineering methodology is O(N) where N is the size of the environment.
Proof 4.4.1
Let the environment consist of
n_{a} analysis steps, n_{d} design steps, n_{i} implementation steps, and n_{t} testing steps.
Let the system acceptance test be the lowest priority step t_{n<<2119>>t}. The number of steps to find a solution is
n_{a} + n_{d} + n_{i} + n_{t} which is O(N).
Corollary 4.5 (WaterSluice: Average Case)
The average case performance of the WaterSluice software engineering methodology is
an orderofmagnitude less than N where N is the size of the environment.
Proof 4.5.1
Let d be the depth of the space. In the special case
of this space d is 4.
Let b be the average fan out of a step in the space if there
was no priority function.
If the space has N steps then
To a reasonable approximation, only the last term is
significant and
Consider the addition of a priority function. The best case
priority function would guide the algorithm directly to
a solution. In this case, the fan out would be 1 and the
total number of steps would be O(1). A worst case
priority function would not guide the algorithm. Thus
the fan out would be b and the total number of steps
would be O(N). In the average case, the priority function would trim the fan out by half. Thus
On average the performance of the algorithm is an orderofmagnitude less
than N.
Table 5.1:
Summary of Completeness
Methodology 
Static Complete 
Dynamic Complete 
Nonmonotonic Complete 

sequential 
yes 
no 
no 

cyclical 
yes 
yes 
no 

WaterSluice 
yes 
yes 
yes 


Table 5.2:
Summary of Performance
Methodology 
Best 
Worst 
Average 

sequential 
O(N) 
O(N) 
O(N) 

cyclical 
O(1) 
O(N) 
O(N) 

WaterSluice 
O(1) 
O(N) 
orderofmagnitude less than N 


Next: Summary Results from the
Up: Supporting Theorems
Previous: An Example of Cyclical
Ronald LeRoi Burback
19981214