merge-sort tree as portrayed in figures through can guide our analysis consider recursive call associated with node of the merge-sort tree the divide step at node is straightforwardthis step runs in time proportional to the size of the sequence for vbased on the use of slicing to create copies of the two list halves we have already observed that the merging step also takes time that is linear in the size of the merged sequence if we let denote the depth of node vthe time spent at node is ( / )since the size of the sequence handled by the recursive call associated with is equal to / looking at the tree more globallyas shown in figure we see thatgiven our definition of "time spent at node,the running time of merge-sort is equal to the sum of the times spent at the nodes of observe that has exactly nodes at depth this simple observation has an important consequencefor it implies that the overall time spent at all the nodes of at depth is ( / )which is (nby proposition the height of is log nthussince the time spent at each of the log levels of is ( )we have the following resultproposition algorithm merge-sort sorts sequence of size in ( log ntimeassuming two elements of can be compared in ( time height time per level (nn / (nn/ (log nn/ / / / (ntotal timeo( log nfigure visual analysis of the running time of merge-sort each node represents the time spent in particular recursive calllabeled with the size of its subproblem