chap lower bounds for examplewhat if we have six items in the listif we break the list into two sublists of three elementsthe cost would be if we break the list into sublist of size two and another of size fourthen the cost would only be with divide and conquerthe best algorithm is the one that minimizes the worknot necessarily the one that balances the input sizes one lesson to learn from this example is that it can be important to pay attention to what happens for small sizes of nbecause any division of the list will eventually produce many small lists we can model all possible divide-and-conquer strategies for this problem with the following recurrence (nmin <= <= - { (kt( ) = = > that iswe want to find way to break up the list that will minimize the total work if we examine various ways of breaking up small listswe will eventually recognize that breaking the list into sublist of size and sublist of size will always produce results as good as any other division this strategy yields the following recurrence = = (nt( this recurrence (and the corresponding algorithmyields (nd / comparisons is this optimalwe now introduce yet another tool to our collection of lower bounds proof techniquesthe state space proof we will model our algorithm by defining state that the algorithm must be in at any given instant we can then define the start statethe end stateand the transitions between states that any algorithm can support from thiswe will reason about the minimum number of states that the algorithm must go through to get from the start to the endto reach state space lower bound at any given instantwe can track the following four categoriesuntestedelements that have not been tested winnerselements that have won at least onceand never lost loserselements that have lost at least onceand never won middleelements that have both won and lost at least once we define the current state to be vector of four values(uwlm for untestedwinnerslosersand middlesrespectively for set of elementsthe