Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Running Time Analysis

The running time of merge sort is determined by the running time of the recursive DoSort routine. (The main DoSort only adds a constant amount of overhead). The running time of the recursive DoSort routine is given by the following recurrence:

  equation44634

where tex2html_wrap_inline70465.

In order to simplify the solution of Equation gif we shall assume that tex2html_wrap_inline58795 for some integer tex2html_wrap_inline61524. Dropping the tex2html_wrap_inline58163s from the equation we get

displaymath70467

which is easily solved by repeated substitution:

eqnarray44644

Therefore, the running time of merge sort is tex2html_wrap_inline59897.

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.