in this figure solid horizontal lines represent the dotted horizontal lines in the quicksort appletsand captions like / cells long indicate averagenot actualline lengths the circled numbers on the left show the order in which the lines are created each series of lines (the eight / linesfor examplecorresponds to level of recursion the initial call to recquicksort(is the first level and makes the first linethe two calls from within the first call--the second level of recursion--make the next two linesand so on if we assume we start with cellsthe results are shown in table table line lengths and recursion recursion level step numbers in figure average line length (cellsnumber of lines total length (cells not shown not shown not shown total where does this division process stopif we keep dividing by and count how many times we do thiswe get the series which is levels of recursion this looks about right on the workshop appletsif you pick some point on the graph and count all the dotted lines directly above and below itthere will be an average of approximately (in figure because not all levels of recursion are shownonly lines intersect any vertical slice of the graph table shows total of cells this is only an approximation because of round-off errorsbut it' close to times the logarithm to the base of which is thus this informal analysis suggests the validity of the *log running time for quicksort more specificallyin the section on partitioningwe found that there should be + comparisons and fewer than / swaps multiplying these quantities by log for various values of gives the results shown in table