each invocation of merge-sort subsequently creates two recursive callsso we can represent this with binary tree each of the child nodes receives sub set of the input ultimately we want to know the total time it takes for the algorithm to complete relative to the size of to begin with we can calculate the amount of work and the number of operations at each level of the tree focusing on the runtime analysisat level the problem is split into two / sub problemsat level there is four / sub problemsand so on the question is when does the recursion bottom outthat iswhen does it reach its base case this is simply when the array is either zero or one the number of recursive levels is exactly the number of times you need to divide by until you get number that is at most this is precisely the definition of log since we are counting the initial recursive call as level the total number of levels is log let' just pause to refine our definitions so far we have been describing the number of elements in our input by the letter this refers to the number of elements in the first level of the recursionthat isthe length of the initial input we are going to need to differentiate between the size of the input at subsequent recursive levels for this we will use the letter or specifically mj for the length of the input at recursive level also there are few details we have overlookedand am sure you are beginning to wonder about for examplewhat happens when / is not an integeror when we have duplicates in our input array it turns out that this does not have an important impact on our analysis herewe will revisit some of the finer details of the merge sort algorithm in design techniques and strategies