worst case analysis is useful because it gives us tight upper bound that our algorithm is guaranteed not to exceed ignoring small constant factorsand lower order terms is really just about ignoring the things thatat large values of the input sizendo not contributein large degreeto the overall run time not only does it make our work mathematically easierit also allows us to focus on the things that are having the most impact on performance we saw with the karatsuba algorithm that the number of multiplication operations increased to the square of the sizenof the input if we have four-digit number the number of multiplication operations is an eight-digit number requires operations typicallythoughwe are not really interested in the behavior of an algorithm at small values of nso we most often ignore factors that increase at slower ratessay linearly with this is because at high values of nthe operations that increase the fastest as we increase nwill dominate we will explain this in more detail with an examplethe merge sort algorithm sorting is the subject of sortinghoweveras precursor and as useful way to learn about runtime performancewe will introduce merge sort here the merge sort algorithm is classic algorithm developed over years ago it is still used widely in many of the most popular sorting libraries it is relatively simple and efficient it is recursive algorithm that uses divide and conquer approach this involves breaking the problem into smaller sub problemsrecursively solving themand then somehow combining the results merge sort is one of the most obvious demonstrations of the divide and conquer paradigm the merge sort algorithm consists of three simple steps recursively sort the left half of the input array recursively sort the right half of the input array merge two sorted sub arrays into one typical problem is sorting list of numbers into numerical order merge sort works by splitting the input into two halves and working on each half in parallel we can illustrate this process schematically with the following diagram