For linear search it makes sense that the run time is big O of N since it will always be one step. As for my understanding of bubble sort it's runtime is O of n^2 this makes sense to me because you'd iterate the number of elements in the an array and each time compare two values till the end of said array.

But for merge sort it's always splitting the data in half, so I'm confused as to explanation as to why the run time is n log n. Additionally I want to clarify my understanding of insertion sorts runtime big O of n^2. Since insertion sort looks for the smallest number then compares it to every single number of the array it would be n^2 because it will loop through the array contents for every iteration.

If I could be given some advice about merge sort, and general understanding of run times that'd be appreciated. I am an absolute newbie and wanted to throw that disclaimer out there.

CodePudding user response：

Let's assume that sorting of an array of N elements is taking T(N) time. In merge sort we know that we need to sort two arrays of N/2 elements (that is 2*T(N/2)) and then merge them (in O(N) time complexity, that is c*N for some constant c). So, T(N) = 2T(N/2) c*N. We could stop here, as it is basically the "equation" you asking about. But let's go a bit further.

To simplify things, we can show that T(N) = kN log N as follows (for some constant k):

Let's substitute T on both sides of the equation we have derived:

kN log N = 2 * k*(N/2) log (N/2) c*N

and expand the right hand side (assuming log with base 2):
= k*N *(log N - log 2) c*N = k*N *(log N - 1) c*N = kNlog N (c-k)N

That is for c=k the equality holds, and it proves that T(N) if of a form kN log N, that is O(N log N)