the advantage of using recursion tree to analyze algorithms is that we can calculate the work done at each level of the recursion how to define this work is simply as the total number of operations and this of course is related to the size of the input it is important to measure and compare the performance of algorithms in platform independent way the actual run time will of course be dependent on the hardware on which it is run counting the number of operations is important because it gives us metric that is directly related to an algorithm' performanceindependent of the platform in generalsince each invocation of merge sort is making two recursive callsthe number of calls is doubling at each level at the same time each of these calls is working on an input that is half of its parents we can formalize this and say thatfor level where is an integer log nthere are two sub problems each of size / to calculate the total number of operationswe need to know the number of operations encompassed by single merge of two sub arrays let' count the number of operations in the previous python code what we are interested in is all the code after the two recursive calls have been made firstlywe have the three assignment operations this is followed by three while loops in the first loop we have an if else statement and within each of are two operationsa comparison followed by an assignment since there are only one of these sets of operations within the if else statementswe can count this block of code as two operations carried out times this is followed by two while loops with an assignment operation each this makes total of operations for each recursion of merge sort since must be at least the upper bound for the number of operations is it has to be said that this has no pretense at being an exact number we could of course decide to count operations in different way we have not counted the increment operations or any of the housekeeping operationshoweverthis is not so important as we are more concerned with the rate of growth of the runtime with respect to at high values of this may seem little daunting since each call of recursive call itself spins off more recursive callsand seemingly explodes exponentially the key fact that makes this manageable is that as the number of recursive calls doublesthe size of each sub problem halves these two opposing forces cancel out nicely as we can demonstrate to calculate the maximum number of operations at each level of the recursion tree we simply multiply the number of sub problems by the number of operations in each sub problem as follows