chap analysis techniques of already proven theorems when the recurrence is of suitable form in particulartypical divide and conquer algorithms such as mergesort yield recurrences of form that fits pattern for which we have ready solution estimating upper and lower bounds the first approach to solving recurrences is to guess the answer and then attempt to prove it correct if correct upper or lower bound estimate is givenan easy induction proof will verify this fact if the proof is successfulthen try to tighten the bound if the induction proof failsthen loosen the bound and try again once the upper and lower bounds matchyou are finished this is useful technique when you are only looking for asymptotic complexities when seeking precise closed-form solution ( you seek the constants for the expression)this method will not be appropriate example use the guessing technique to find the asymptotic bounds for mergesortwhose running time is described by the equation ( ( / nt( we begin by guessing that this recurrence has an upper bound in ( to be more preciseassume that ( < we prove this guess is correct by induction in this proofwe assume that is power of twoto make the calculations easy for the base caset( < for the induction stepwe need to show that ( < implies that ( the induction hypothesis is ( < for all < it follows that ( ( < < <( ) which is what we wanted to prove thust(nis in ( is ( good estimatein the next-to-last step we went from + to the much larger this suggests that ( is high estimate if we guess something smallersuch as ( <cn for some constant cit should be clear that this cannot work because cn and there is no room for