Fundamentals Of Iterative Theory

Iterative Theory is a study of trying to ‘solve a problem all in one go’ versus trying to ‘solve it by splitting it up into parts’.

Iterative theory is not about comparing different project management or problem solving methodologies.  At it’s most basic Iterative Theory does not care what methodology you are using – but it does care how you apply that methodology.

This post is an introduction in applying Iterative Theory to Structured Stochastic Problems.  In later posts we will develop an argument to show that there is an unavoidable additional cost incurred in removing the ambiguity inherent in a project.  We will then see how to minimise that extra cost through the use of Iterations.

Abstract Version

As a first step consider splitting a project into several parts.  Clearly if it cannot be split up then you have no opportunity to take an iterative approach.  But let’s assume we can split it up into parts.  What does this mean?  It means that for each part we can run our methodology on that part alone and then when that part is done move onto the next part and repeat the process.

So a fundamental of Iterative Theory is that we must have a problem that we can split into parts.

Iterative Theory assumes some level of ignorance or uncertainty on the side of the problem solver.  If there is no uncertainty – in other words I can prove that my proposed solution is correct – then there will be no benefit in splitting it into iterations.  There is a subtlety here in that I may well be able to prove that my proposed solution exactly satisfies the problem as it has been given to me – but that does not help if there is some uncertainty regarding the accuracy of the initial statement of the problem.

So a fundamental of Iterative Theory is that there must be some uncertainty in the correctness of the solution.

Iterative Theory also requires an ‘Oracle’ to tell us if we have got it right.  The Oracle represents the external source of truth regarding the solution.  Only through presentation of a real solution can we know for sure that we have got it right.  This is closely related to the concept of parts; what we really mean by being able to split a project into parts is that our Oracle can establish the correctness of the parts as they come.

So a fundamental of Iterative Theory is that there is some Oracle that can tell us if each part of the solution is correct.

Iterative Theory also requires that there is some connection between the parts of the problem.  The connection manifests itself in the way that feedback from earlier parts of the problem alters the possibilities on later parts of the problem.  If there is no connection between the different parts of the problem then applying iterative theory will not help.

So a fundamental of Iterative Theory is that the parts of the problem are interconnected.

Iterative Theory is about the impact of using iterations on the efficiency of a project or problem solving exercise.  This links back to the role of the Oracle in that if the Oracle tells us we have got it wrong then there must be some form of penalty.  If we can try as many solutions as we like with no penalty then it does not matter if we have a good approach or bad approach.

So a fundamental of Iterative Theory is that there is a penalty for getting it wrong.

Taking all of these fundamentals together we can say that Iterative Theory is about ‘Solving Stochastic Structured Problems Efficiently’.  Lets break this definition down and look at each part individually:

• A Structured Problem is one where there are many individual parts to it and they depend upon each other.
• To know that we have Solved a part of the problem we need an Oracle who can provide feedback as we go along.
• Stochastic means that there must be an element of uncertainty regarding the possible solutions for the individual parts.
• And Efficiently means that there is an incentive to find a cost effective approach to solving the problem.

I will use the abbreviation ‘SSP’ for a Stochastic Structured Problem.

As we will see when it comes to project management you have a choice to treat the project as an SSP or not irrespective of the nature of the problem itself.  What I mean by this is that you can easily mismatch your approach to the problem that you have.  Getting this wrong ie adopting a predictive approach can lead to significant inefficiency.

Solving a problem that is an SSP is a pretty sophisticated challenge.  Before getting into that we will be starting with simpler types of problems according to the following problem classification scheme:

	Simple	Structured
Deterministic (Fixed)	Simple Deterministic	Structured Deterministic
Stochastic (Random)	Simple Stochastic	Structured Stochastic

In studying the decision making process we will work our way around this matrix starting from the top left and working to the bottom right.  Having already spent time on the Structured Stochastic case lets have a quick look at the other boxes.

A Simple Deterministic problem is one where each decision can be made in isolation ie each decision is independent of any of the others.  Moreover it is completely deterministic in that whatever choice we make will have a given pre-determined outcome.  Problems like this are amenable to a simple approach at finding a solution; if each choice has a fixed consequence we just need to consider each choice in turn and then choose the best one.

A Simple Stochastic problem is one where we can still make each decision in isolation.  However there is an element of chance involved in that for each decision we make there are a range of possible outcomes.  Problems like this are solved by considering the probabilities of the various outcomes.  By analysing the most and least likely outcomes of our decision we can make the ‘best’ choice.  This type of problem is the staple of Decision Theory that we will examine in more detail later.

A Structured Deterministic problem is one where there is no uncertainty but there are a lot of interdependent decisions to be made.  The more decisions there are to be made the harder it gets to solve such a problem because there are more and more possible combinations to consider.  The lack of randomness is a blessing but even so such problems are usually very hard to solve in practice.  The Travelling Salesman problem is a classic example of this type of problem.

And finally we are back to Stochastic Structured problems.  These types of problems are naturally the most difficult to solve and their analysis is a major part of Iterative Theory.  Most real world problems are of this type.

Practical Examples

Now lets look at some examples that will (hopefully!) help clarify all of this.

Playing Chess. This problem is made up of many parts – the moves that will be made.  Also the moves you make depend upon each other.  The element of chance comes from the moves your opponent makes.  Some moves are good and some are bad.  Hence (in practical terms) this is an SSP.  In a later post we will consider the impact of your opponents moves – that takes us into Game Theory– and how the goal of our opponent affects our strategy.

Betting on a horse race. This is not an SSP as we are only making a single decision.  The only ‘part’ of the problem is which horse we bet on.  The factors affecting the outcome of the race may well be complex but because we are only making one decision it is not an SSP.

Building a House.  This is an SSP as there are many parts to a house and they definitely depend on each other.  The element of chance is introduced through potential mismatches of plans vs reality and other unforeseen circumstances during construction.  A change in one part may well lead on to changes elsewhere.  Of course, if the plans turn out to be completely accurate and there are no surprises then it is not an SSP.

Planning a Journey.  This can be an SSP if for instance several modes of transport are used.  The uncertainty is introduced through the potential for traffic jams, train cancellations etc. and the dependency of later decisions on previous ones through missed connections.

Playing Roulette. This is not an SSP simply because each decision is independent of the one before. The lack of dependency turns this into a series of simple problems.

Playing a hole of Golf. If we say that the decisions to be made are which club to use to take each shot then this is an SSP.  The best club to use clearly depends upon the somewhat random (especially if you are me) result of the previous shot.

Decimal expansion of Pi. While it may in fact be quite difficult to work out one by one what the digits of Pi are there certainly exist algorithms to do so.  There is no element of randomness involved.  Therefore this is not an SSP.

General Themes

It is possible for a problem to become Structured if we have to repeat it several times – provided something can be learnt from earlier outcomes to inform later ones.  For instance, taking the Horse Racing example, if we are going to make several bets we might start to learn things from earlier races that would alter our decisions on later ones.  Maybe a particular jockey is having a good day.  Or horses starting on the outside are consistently doing worse than expected.  However if we take the Roulette example – assuming it is perfectly fair – then there is nothing to be gained from earlier spins to inform later ones.

Simple does not refer to the potential difficulty in making up your mind or taking all the variables into account but to the fact that there is no dependency between decisions.  For instance in the Chess example the decision for any one particular move is Simple.  It may be that to work out the best move would defeat the most powerful computer in the world but without the chance to take advantage of feedback this single move is not a Stochastic Structured Problem.

Another important theme is feedback.  For a problem to be Structured there must be feedback after each decision that can be used to inform subsequent decisions.  In the Golf example the feedback comes from where the ball ends up after each shot.  If you had to decide which club to use for each shot up front then the problem would not be Structured.  While you can see the feedback after each shot you are not allowed to act upon it.  The approach taken makes the problem into a simple one with only a single decision being made up front.

In the Roulette example while you get feedback after each bet it is useless to you as it does not provide any information regarding future bets.  It is important that the feedback comes from an external source or ‘Oracle’.  If you can work out what the feedback will be for your decision before you make it then the problem is not a Structured one.  In the π example while the actual value of the next digit might seem random you know from your algorithm that it will be correct.  So the problem is not an SSP.

Feedback is required to resolve the uncertainty.  In the Journey example the uncertainty is provided by the vagaries of the transport system.  In the Chess example it is caused by the potential responses of your opponent.  This is a sliding scale; you might argue that in the Building example there is very little uncertainty hence it is ‘only just’ a Stochastic Structured Problem.

There is an element of subjectivity in the classification of a problem.  It may be that a Structured Problem for one person is not structured for another.  It will depend upon your level of knowledge which will affect how you Frame the problem.

We have five factors to consider when classifying a problem as being an interesting Stochastic Structured Problem:

1. Is there a clearly defined goal or way of deciding better or worse outcomes?
2. Is there a single decision to be made or many?
3. Is there some uncertainty in the outcomes given your decisions?
4. Is there an interdependency between the outcomes of each decision?
5. Is there any opportunity for useful feedback before reaching the goal?

If a problem satisfies these five requirements then it is a Stochastic Structured Problem and we can apply Iterative theory.

Virtually all real life projects satisfy these requirements.

The Dice Game

In this Post I am going to introduce ‘The Dice Game’.  This game has many variants.  In this version of the game you can throw as many or as few dice as you like and you score points in the following way:  you add up all the numbers on the dice that you throw unless one or more of them turns out as a 1.  If that happens then you score nothing that turn.

Here is my bag of dice:

A couple of examples;  If I throw three dice and they are 6,3,2 then I would score 11 points.

If I throw five dice and get 3,5,1,2,1 then I would score nothing because two 1s have turned up.

You finish the game when you reach a target score of say 100 points.  The big question in this game is how many dice should I throw to reach the target in as few turns as possible?

A couple of preliminaries.  For a single die there are six equally likely possibilities.  Usually for a die the average score is 3½ but in our case it is 4 if we do not throw a 1 and zero if we do.  This gives a slightly lower average of 3⅓ as I have attempted to explain in the following diagram:

Let’s consider some extreme cases; one option would be to throw one dice at a time.  In that case it would take on average 33⅓ throws to get there.  Another option would be to throw 50 dice at once.  In this case although we guarantee getting there in one throw (as every die must count at least 2 points) it is very unlikely to count at all;  Surely one of those 50 dice will be a 1.  It turns out that on average it would take around 10,000 throws this way.

If we throw too few dice it takes a long time to get there (as each throw scores too little) and similarly if we throw too many dice it also takes a long time (as it is unlikely to score at all).

What is the best number of dice to throw then?  We can use some simple Probability Theory to work that out. The only way for our throw to score is if none of the dice are a 1.  Each die has a probability of 5/6 of not being a 1.  Each die has an average score of 4 if it is not a 1.  For a number, say, k, dice we have to add all the scores and multiply all the probabilities together to find that on average our score S will be:

We can plot a graph of this:

Looking at the graph we can see that the maximum average score is when we throw 5 or 6 dice.  In both cases we expect to score 8 on average.  Throwing more dice means we are too likely to get a 1 and throwing less dice means we are not scoring enough for each successful throw.  Thus with the optimal strategy it would take between 12 and 13 throws to win on average.

We could play this game instead with coins.  Throw as many coins as you like getting one point for every head but if one of them is a tail then you score nothing. In this case the probability of success per coin is ½.

Or we could play with cards.  Imagine a shuffled pack of playing cards (with no Jokers).  You choose how many cards to be dealt.  You get one point for every card unless there is an Ace;  in which case you score nothing.  In this case the probability of success per card is 12/13.

Generalising

If there are k objects each with a probability p of success then on average your score will be:

We are keeping things simple here and assuming that our score per object is 1 if we are successful and zero if not.  This assumption does not affect the conclusions we will come to.

If we examine this equation we can see that it is made up of the two parts k and p^k (p to the power k – sometimes written p^k).  The first (blue line) increases with k and the second (orange line) decreases with k as shown in the graph below.

The combination of these effects gives rise to a humped shape (the yellow line) which represents our average score.  Hence there must be an optimum value for k.  By differentiation of equation (2) we find that the optimum number of objects to throw each turn k_max is given by:

where ln(p) is the natural logarithm of p.

By way of example with the Dice Game where p is 5/6 we find that k_max is 5.48.  As we can only throw a whole number of dice it is natural for this to be halfway between throwing either 5 or 6 dice as we saw before.

With the Coin Game variant where p is ½ we find that k_max is 1.44.  Looking at throwing one coin our expected score would be ½ and throwing two coins it would also be ½.  Any more coins would be worse than this.

Lets plot a graph of k_max as a function of p:

Looking at this graph we can see that as your probability of success per object starts to approach 1 then the number of objects to throw starts rapidly to increase.  Indeed if p is 0.95 then k_max is 19.5.

For larger values of p we can make a rather neat approximation to k_max by considering the probability of failure instead of the probability of success.  Let’s call the probability of failure q (where naturally p+q=1).  For the Dice Game q would be 1/6 and for the Coin Game q would be ½ and the Card Game it would be 1/13.

It turns out that for q<1/2:

This is a pretty accurate and quick rule of thumb to estimate the optimum number to throw for situations where we have small q.  For instance with the Dice Game q=1/6 and you should throw 6 dice;  for the Coin Game q=1/2 and you should throw 2 coins and in the Card Game q=1/13 and you should take 13 cards per hand.

This is a very general rule (where q<1/2):

If my chance of failure per object is q then I should try 1/q objects per turn.

Using this rule will get you the most points per turn.

As A Game

The rule is fine when you are far away from the target and have no realistic chance of getting there in a single throw.  But once you get near your target you might want to adapt to a different rule;  one that tells you the best number of objects to throw in order to obtain a particular score.  For instance if I was only 1 point away from the target then I would only throw one object in order to maximise my chances of scoring something.

Note that as described this is a single player game.  The strategy can change significantly if we have an opponent and the winner is the first one to reach the target.  Then our optimal strategy would definitely depend on what our opponent is likely to do and what his score currently is and what my score is.  This takes us into the realm of Game Theory which we will look at later as an extension of Decision Theory.

Also a a game I play it slightly differently;  usually a turn is made by throwing one die at a time and adding up your score.  At any point you can stop and bank what you have scored so far or risk another throw, which if it turns out to be a 1 means you lose your score this turn and it then moves on to the next players go.  It’s more exciting this way.  Also, I would reduce the target to say 50 points instead of 100 as that goes on a bit too long.

Iterative Theory

The Dice Game gives us one way of looking at how big our Iterations should be.  The analogy is not at all perfect but:

• When we deliver software there is always the chance of an error.
• The more things we put into the Iteration the more likely there is to be an error.
• On the other hand the more we put into each Iteration the faster we can go.

If each requirement has a 95% chance of being correct (or equivalently 5% chance of being wrong) then I would try 20 requirements per Iteration.  If my requirements have a 50:50 chance of being right or wrong then I should only do 1 or 2 per Iteration.

Note that we do not have to limit ourselves specifically to Requirements with this analogy.  We could be talking about anything where we have the option of delivering it in parts.

It seems that the Dice Game can give us an idea of where to put the balance between being greedy to score more points and being realistic in what we can achieve.  I hope to say more on the link between the Dice Game and Iterative Theory in later Posts.  There are other arguments that lead to the same conclusion as equation (3) on the optimum Iteration size.

Also, you may note that k_max is the inverse of the Shannon Information Entropy associated with p.  We will most certainly be discussing Information Entropy in later Posts.

Requirements Decay

The line of thinking in this Post was prompted by noticing the disparity between the set of requirements given at the start of a project with the functionality actually implemented at the end.

Rule of Thirds

What I noticed across several projects was the ‘rule of thirds’.  That is in the final system one third of it is in the original plan, one third is in there but very different to how it was envisaged and the final third was not in the original plan at all.  It is made up of new requirements that were not considered at the start.

Upon investigation it was not that the requirements were “wrong” but that the world had moved on since they were written.  Ah the benefit of Hindsight.

It occurred to me that there is a similarity between system requirements and radioactive decay.

Requirements Decay

The idea is that as soon as a requirement is defined it suffers a risk that it will ‘decay’.  This decay is not to be confused with discovering a bug but instead is where the requirement itself becomes wrong.

As a system is developed it gets bigger in terms of the number of requirements it contains.  Now, the bigger a system is the greater the rate of requirements decay.  Eventually you reach a point where you are adding requirements just as fast as they are decaying; this can be categorised as ‘maintenance mode’  i.e. the system stays at roughly the same size (in terms of functionality) but requires work to keep it there.

Iterative Theory

We can gain some insight modeling this situation with Iterative Theory. What we do is assume the system is being built in Iterations and then vary the Iteration length and see what happens.

Some Modelling

You can skip the maths and jump ahead if you like; I have included it here because it is fun.

If a team has an absolute velocity of v then that means they are able to implement v individual requirements per unit time.  This is different from normal velocity which is a measure of the number of requirements per Iteration.  As usual for the sake of simplicity I am assuming that every requirement is roughly the same size.

Lets also give all of the requirements a mean lifetime of τ (pronounced tau).  This again is for simplicity.

We could talk about the half life t_1/2 of the requirements as the time it takes for half of the requirements to decay.  It is certainly easier to think about than the mean lifetime.  Fortunately the two are related:

We can now introduce the iteration length Δt and start building our software iteration by iteration.

We are able to develop v.Δt requirements in the first Iteration – but a percentage of them will decay while we are doing this.  By the end of the first Iteration we will expect to have this many requirements left:

Because we are developing Iteratively we can start the second Iteration with a fresh set of requirements.  We are not stuck with the requirements as they were originally envisaged at the beginning of the project.  So the second set of requirements only begin to decay from the point at which we begin the second Iteration.

By the end of the second Iteration we have added another set of requirements but some more of the first lot have decayed while we were doing that.  So now only:

of the first set of requirements are left.  In fact at the end of each Iteration we loose a constant factor:

of however many requirements there are.

If we extend this process on and on then eventually we reach equilibrium; the number of fresh requirements we are adding each Iteration exactly balances the number decaying from all the previous Iterations put together.

We can work out how many requirements R we have left at any given time T.  It turns out to be:

T is the total time that has passed since we started the project.  Note: This equation smooths out the jumps that occur at the end of each Iteration so in effect it overestimates how many requirements we actually have.  This effect can be seen in the graph below.   But that does not matter for the thrust of the argument – it just makes the maths a bit simpler.

This Graph shows system growth for two projects one with Iterations of tw0-weeks and the other Iterations of a year.  The half life t_1/2 of the requirements in both cases is one year.  The absolute velocity v is the same in both cases.

We can see that in the case of two-week Iterations the total size of the system increases quite quickly at the start and then gets slower and slower until it stops.  The one year Iteration project clearly shows the jumps as each Iteration is released and the deacay that occurs in between.  In the long run as T gets very large then:

This does not depend on T and represents the upper limit on the size of the system where effectively it is in pure maintenance mode. The only way to get a bigger system is to either increase your velocity v or reduce your iteration length Δt – assuming you can do nothing about the requirement half life.  On the other hand if your velocity decreases or your Iterations get longer then the size of the system will quickly drop.  This effect can be seen in the one year graph.

In the limit of Δt being significantly smaller than τ we find:

So with short Iterations – in other words an incremental approach – as T increases we reach the maximum possible system size of:

In words this makes sense; the maximum system sizze is the product of the velocity and the mean lifetime of the requirements.  However the longer your Iterations are the more it limits your total system size.  In fact:

So it would seem that with longer iterations your total system size is limited to being one half of an iterations worth of functionality smaller than it could be.  This does not matter if your iterations are short but becomes significant as they get bigger.

Enough Maths Already

If you skipped here from above what you missed was:

If

• Requirements suffer from ‘Requirements Decay’

Then

• Shorter Iterations let you build a system to a given size faster
• Shorter Iterations let you support a larger system for the same cost

Half Life

The question arises, what is the half life of requirements?  Really this can only be determined empirically within a given systems context.  I have evidence that in my field (derivatives trading systems) that the half life is around a year giving a mean lifetime per requirement of around 18 months for a new system.

Thus a system that takes one year from requirements definition to deployment (developed as a single Iteration with no tinkering of requirements in the middle) will be only 50% complete by the original planned delivery date. With Iterations of two weeks duration the system would be 75% complete after the first year.

This discrepancy continues in the long run.   For a given velocity using two week Iterations would let you support a system almost 50% larger than one with an Iteration length of a year!

Cost

The cost of a system is proportional to the absolute velocity v and the total time that has passed ‘T‘.  So, going back to our example above a system with 2 week iterations would be around 66% the developer cost of a system with one year Iterations not only to build up to a certain size but to maintain at that size going forwards.

Looking at it the other way around the efficiency of the team goes up as the Iteration length shortens.

Lean

A few thoughts from Lean development.  The longer your Iterations are the more waste there is in each Iteration.  Certainly Lean thinking implies having as short Iterations as possible.

Real Options

A few thoughts from Real Options.  Shortening the Iteration length means postponing your decision about what requirements to develop.  This means you can make better choices later.  In other words there is value in postponing the development of a requirement until the ‘last responsible moment’.  By accepting long Iterations you are forced to make early decisions about what to build long in advance of when it will be delivered – only to find it is no longer needed by the time you finish.

Automate Your Testing

In this post we will use Iterative Theory to examine the impact of Iterations on the cost of testing.

Let us assume that we have N requirements.  Let us also assume that they are all roughly the same size in the sense of costing the same to test.

If we take a waterfall approach to this project we develop the entire system in one Iteration. Once developed it needs to be tested before we can ‘go live’ with it.  Clearly the cost of testing such a system is proportional to its size; if a single requirement costs m to test then the total system costs Nm.

But what if we introduce intermediate Iterations?  This means we will ‘go live’ with the system after each Iteration.  ‘Going live’ with the system at these intermediate stages – and getting real world feedback – is what distinguishes an Iterative approach from a waterfall one. If we did not bother ‘going live’ (or testing) until all the Iterations were completed then we would be acting no differently from a waterfall approach.

After each Iteration we have to test the system we have so far.  This would include re-testing everything added in previous Iterations as well.  This is because when we add new functionality to a system we have to test that we have not screwed up something that was already there and working.

If we take an incremental approach of one requirement at a time the first Iteration would cost m to test, the second 2m, the third 3m etc. until the last Iteration which would cost Nm to test.

If we add up all of these costs we find the total cost of testing for the incremental approach:

The total cost of testing for the project is now increasing  like N² (N squared) rather than N as it was with a single Iteration approach.  This is a big problem.  For a modest size project with 100 pieces of functionality that would mean an incremental approach would spend roughly 50 times as much on testing!  The large number of Iterations drives up the cost by repeating the same tests again and again and again.

This puts a lot of pressure on a project to have Iterations that are as large as possible.

But in Agile software development there is a get out clause.  What Agile software development says is that all testing should be automated.  There is an initial cost associated with automating the testing of a requirement but repeating the test costs nothing.  Moreover in an Agile project you would define the requirement in terms of tests – particularly handy when it comes to automating them.

Now what happens to our cost if we start automating the testing?  Let us assume that the average cost associated with automating a test is a.  Now the cost of testing is Na.  In fact the cost of automated testing is independent of the size of the Iterations used.

But what if the cost of automating a test is greater than the cost of doing it manually?  This seems a reasonable assumption to me and I would wager is true in virtually all cases (ignoring test driven development for the moment).

So, I am taking an Iterative approach and I have a choice; do I do manual testing or automated testing?  In the following example automated testing costs 10 times as much as the equivalent manual test.

Initially Manual testing looks cheaper.  However beware – this is also a trap!

Eventually the cost of manual testing will catch up with that of automated testing and start to exceed it.

The crossover point can be calculated as a function of a and m and occurs when

In our example as a=10m this is at the 19th Iteration.

In fact no matter what the values of a and m are once N is large enough the manual testing cost will always dwarf that of the automated testing cost.

But beware!  At any particular Iteration we have the choice of automating the testing for the feature we are adding or just doing it manually.  As manual testing is cheaper than automated testing – and possibly quicker – perhaps just this once we should forgo the automated testing?   The same argument applies to the next Iteration and the next and so on.  This short term view encourages the behaviour of not doing automated testing and falling into the trap mentioned above.

The manual testing cost of any particular ‘go live’ quickly starts to become prohibitive.  After all it increases with each Iteration (as it is proportional to the size of the system so far) whereas the extra automated cost is fixed at a per Iteration.   This encourages the behaviour of not doing releases so often effectively increasing the size of the Iterations being used.

Lets look at it the other way.  Can we conclude then that it is OK to do manual testing provided:

After all in this regime won’t the manual approach be cheaper?

The safe answer to this question is ‘no’.  Eventually you would imagine that the system being developed would enter maintenance mode.  In maintenance mode it is not about adding new functionality – so we can imagine N is fixed – but rather about modifying what is already there.  So the system is not really getting any larger but on the other hand releases are still required.

In maintenance mode every release still requires testing of the entire system.  The manual testing cost of Nm just keeps on repeating the longer the system lives.  On the other hand automated testing is almost free.  But not quite free;  we have to pay for fixing up the automated tests related to the maintenance changes.

If we assume that a fraction f of the system changes with each maintenance release then it will cost fNa for each release.  So provided

then automation will still be cheaper.  For any system with a small percentage of maintenance the additional automation cost will be lower than the cost of manually re-testing the entire system.

But we are left with a loophole.  Provided that either conditions (3) or  (4) hold then manual testing looks like the better option.

This view can only be justified in special circumstances.  If you have a system that is small with a short shelf life.  Like prototype or proof of concept systems.  Systems designed to be built quickly and thrown away.  Or if you have a system where the ‘churn’ due to maintenance means that previously automated tests become redundant  so rapidly that you fail to get the benefit of them (In other words you do not know what you are doing).

You could try to make the argument for manual testing by using very large Iterations.  However we have to ask ourselves what is the chance of passing all of the tests without any failures?  In theory a single failing test would cause us to recall the system, fix it and then have to test the whole thing again!  Moreover with very large Iterations I am likely to have to go through several rounds of testing and re-testing to get the system right.  All this re-testing is going to start to become expensive if none of it is automated!  And to make matters worse the larger the Iterations the more times I am likely to need to re-test it.

The same situation applies for maintenance.   It is unlikely that we would have to test a system just the once for a ‘go live’.  Thus equation (4) represent a best case scenario for manual testing.  In particular the more ‘churn’ there is the more likely multiple re-tests will be required.  Such re-testing will be expensive.

We will look at the impact of the probability of test failure in more detail.  In a later Post we will see that an argument can be made that – if you have to do it – there is an optimum size of Iteration to use for Manual testing.

I skipped over Test Driven Development (TDD) earlier – quite deliberately.  The argument above for automated testing is quite sufficient to show it’s desirability without the need to mention TDD.  You can think of TDD as a way of reducing the factor a that is used.  This brings the crossover point down and means that the benefits of automation arrive sooner.  It also increases the factor f meaning you can cope with more ‘churn’ in maintenance.

In fact if you can get to the point where a<m then there is benefit immediately for the first iteration and subsequently for any and all maintenance changes!

Conclusions For Iterative Projects:

• For an Iterative project the cost of manual testing will eventually outstrip that of automated testing.
• Discipline is required to avoid falling into the recurring trap that ‘for this Iteration’ the manual tests are cheaper.
• Even if Manual testing might seem cheaper this will likely not be the case when re-testing is taken into account.

Although applied to testing the same argument applies to any cost associated with the project that a) needs to be repeated each Iteration and b) is proportional to the size of the project so far and c) can be automated or eliminated for a price proportional to the size of the Iteration

How Many Ways Can A Project Be Done?

On a software project the scope is usually defined in terms of Requirements. Later I will talk about Requirements from the point of view of Iterative Theory but for now lets just assume that I have a set of requirements that define the project.

Each requirement is a specific piece of functionality that the system needs to have. Assuming that all of these requirements can be implemented independently and in any order the question naturally arises – How many ways can this be done?

Let’s start by assuming that we have N individual requirements.

In a Waterfall model we would tackle all N requirements at once. In Iterative Theory this means using a single Iteration of size N for the project. Clearly in terms of Iterations there is only one way such a project can be done.

In an Incremental model we would do the requirements one at a time. In Iterative Theory this means using N Iterations of size 1. For the first Iteration we have a choice of N requirements, for the second one of the remaining (N-1) etc giving us N! (pronounced ‘N factorial’) different ways of doing the project. This corresponds to the total number of possible permutations of the N requirements.

N! gets big really fast. For instance 5! is 120. That means for a project with only 5 requirements we have over 120 different ways to do it. For 10 requirements we have 10! which is 3,628,800 ways to do it! No wonder the ! symbol is used to represent the factorial function. In fact N! increases faster than all polynomial or exponential functions.

But for most projects we would actually choose Iterations consisting of a number of requirements done together. If we assume that there are say k requirements per Iteration then how many ways are there of doing our project?

Using fixed size Iterations of size k is a bit trickier. For the first iteration we can choose k from N requirements; then for the second we again choose k from the (N-k) remaining until we reach the last iteration which will have k or fewer requirements.

What you end up with is W_k(N,k):

where [x] is the integer value of x; e.g. [4.32] = 4.

We can simplify this somewhat by only considering cases where k is an exact divisor of N; this removes to tricky last Iteration with a different size to the rest. In that case we find:

The k! comes from the number of permutations within an Iteration and the N/k from the number of Iterations.

W_k varies between the two extremes we have seen; it has it’s minimum value of 1 when k=N i.e. we are taking a Waterfall approach and it’s maximum value when k=1 i.e. we are taking an Incremental approach.

Finally we can consider what happens if we allow Iterations to vary in size as we go. For instance we might choose to do one requirement in the first Iteration, then three in the next, then two etc. If we do that then we end up with a pretty tricky problem! However through a bit of coding it can be shown that the first few terms in the series for N=1, N=2, N=3 etc are:

1, 3, 13, 75, 541, 4683, …

A quick search on google and this turns out to be the Sloane series A000670 which also represents amongst other things ‘the number of ways a horse race can be won if ties are allowed’. I have never thought about it before – a two horse race can finish in three different ways.

This leads to an approximation for W_V(N):

This is a truly astronomically increasing function of N – in particular because ln 2 < 1.

It is worth considering for a moment how many requirements you would need to have more ways of doing your project than there are atoms in the universe. There are estimated to be 10⁸⁰ atoms in the Universe. That means for an Incremental approach you would need 59 requirements and for the ‘variable’ approach it would be 55. In a more realistic situation with say 5 requirements per Iteration then it would be 77 requirements.

With any kind of Iterative approach there are literally an astronomical number of ways of tackling a project of any reasonable size. It naturally leads to the questions:

• Which is the best order to do the requirements in?
• How big should my Iterations be?

In an Agile approach the answers would be ‘do the ones that add the most value first’ in some combination with ‘do the riskiest ones first’. We will use Iterative Theory to gain insight into these rules and perhaps answer these important questions.

Methodologies

Traditional approaches to project management are predictive.  Through analysis and design we create a prediction of what a full and complete solution will be. We then proceed on the assumption that our prediction will be correct.

More modern Agile approaches would be adaptive.  With these approaches we would take a piece of the problem, try it out and then adapt our design based on the feedback we receive.  We still make predictions but the crucial thing is that we reserve the right to adapt by making new predictions based on feedback.

Finally we can consider reactive approaches.  In these we do not particularly bother with any predictions above and beyond that required for whatever seems most important right now.

A fully predictive approach will attempt a solution in a single iteration – a single giant step.  An adaptive approach will break the problem up into several iterations attempting to build a solution in stages.  A reactive approach will use tiny iterations and evolve a solution incrementally.

In Iterative Theory these approaches form a spectrum of possibilities with the variable factor being the size of the iteration and hence the frequency of feedback.

The terms ‘predictive’, ‘adaptive’ and ‘reactive’ are chosen specifically to illustrate the type of psychology usually associated with the different approaches.

With predictive we try to ‘dot every i and cross every t’ before we actually start building or doing anything (apart from planning!).  With adaptive it implies that we have ‘a learning mechanism in place’ to utilise the feedback we get in a positive way.  With reactive it implies that we  ‘do not plan at all’  (but we get feedback all the time).

In Iterative Theory we focus on the impact of varying the size of the Iterations – no matter the psychology employed.  We will quantify the efficiency in terms of the costs associated with the project.  Primarily these costs are incurred through errors in our proposed solution and overheads associated with the act of delivery.  And costs do not care about psychology.

For those that cannot wait we will (eventually) see that:

• You would be mad to adopt a fully predictive approach
• Provided overheads are low then a reactive approach is best
• But the most practical approach is adaptive shifting to reactive in time

I hope you will end up convinced of the benefits of an Iterative approach.