recursion to formalize this argumentwe can define the nesting level of each entry such that the entry on which we begin has nesting level entries stored directly within it have nesting level entries stored within those entries have nesting level and so on we can prove by induction that there is exactly one recursive invocation of disk usage upon each entry at nesting level as base casewhen the only recursive invocation made is the initial one as the inductive steponce we know there is exactly one recursive invocation for each entry at nesting level kwe can claim that there is exactly one invocation for each entry at nesting level kmade within the for loop for the entry at level that contains having established that there is one recursive call for each entry of the file systemwe return to the question of the overall computation time for the algorithm it would be great if we could argue that we spend ( time in any single invocation of the functionbut that is not the case while there are constant number of steps reflect in the call to os path getsize to compute the disk usage directly at that entrywhen the entry is directorythe body of the disk usage function includes for loop that iterates over all entries that are contained within that directory in the worst caseit is possible that one entry includes others based on this reasoningwe could conclude that there are (nrecursive callseach of which runs in (ntimeleading to an overall running time that is ( while this upper bound is technically trueit is not tight upper bound remarkablywe can prove the stronger bound that the recursive algorithm for disk usage completes in (ntimethe weaker bound was pessimistic because it assumed worst-case number of entries for each directory while it is possible that some directories contain number of entries proportional to nthey cannot all contain that many to prove the stronger claimwe choose to consider the overall number of iterations of the for loop across all recursive calls we claim there are precisely such iteration of that loop overall we base this claim on the fact that each iteration of that loop makes recursive call to disk usageand yet we have already concluded that there are total of calls to disk usage (including the original callwe therefore conclude that there are (nrecursive callseach of which uses ( time outside the loopand that the overall number of operations due to the loop is (nsumming all of these boundsthe overall number of operations is (nthe argument we have made is more advanced than with the earlier examples of recursion the idea that we can sometimes get tighter bound on series of operations by considering the cumulative effectrather than assuming that each achieves worst case is technique called amortizationwe will see further example of such analysis in section furthermorea file system is an implicit example of data structure known as treeand our disk usage algorithm is really manifestation of more general algorithm known as tree traversal trees will be the focus of and our argument about the (nrunning time of the disk usage algorithm will be generalized for tree traversals in section