# How does the dividing Step in Merge Sort have Constant Time Complexity?

I am highly confuse while calculating time complexity of Merge Sort Algorithm. Specifically on the Dividing Step. In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".

How it will take constant time. If we assume that divide is an elementary operation and take very less time, then also we should include the time taken by divide.

Suppose If we have to divide very large amount of time then it must be consider while calculating the time complexity. According to me Number of divides depends on "n" i.e. Calculating mid point depends on the array size "n".

For Example,

if n = 2

Number of divides required = 1

if n = 4

Number of divides required = 3

if n = 8

Number of divides required = 7

if n = 16

Number of divides required = 15 and so on....

According to me,

If Recursively Define:-

Number of Divide needed for "n" (input array length = n) <= 1 + Number of divides needed for (n-1). {when n = 0 Number of divides = 0 when n = 1 Number of divides = 0}

Or..........

Number of Divide needed for "n" (input array length = n) <= (Summation of 2^i from 0 to n-1) - (2^n)

So, it depends on "n". So how we can take it as a constant time????

• Possible duplicate of What is O(...) and how do I calculate it?
– gnat
Sep 26, 2016 at 13:00
• @Ordous then how we write the complexity of Dividing stem is Big O(1) Sep 26, 2016 at 13:05
• Right, sorry, I confused it with quicksort. It is constant. We would need a number of divide steps, however at each recursion level, we would need much more merge time than divide time (logn vs n), so it's discarded from final analysis as a minor term. Sep 26, 2016 at 13:12
• We do this in final calculation but in every book even in CLRS it is specifically written that in dividing step it will take constant time Sep 26, 2016 at 13:16
• Integer Division is usually treated as a constant time operation for complexity calculations. That is, n/2 is one operation. In practice, division in modern CPUs don't vary much on input length, at least up to largest machine usable word / multi word operation. Oct 17, 2016 at 9:30

I'm glad you took the time to try to understand this apparent discrepancy. You're correct that we do need to account for the divisions, and that for this algorithm, we have `~n` divisions. In general, if we are dividing reasonably small numbers (those that fit in a long), we count that individual division operation as effectively `O(1)`, so we have `O(n)` divisions.

What you're missing is that it doesn't really matter, because we already have an `O(n)` operation in the mix: the merge. In this particular case, that's why adding the divisions in doesn't change the overall complexity from `O(n log n)`. Accounting for the divisions would change it to `O(2n log n)` and constants get factored out.

• I am not talking about whole merge sort algorithm I am only talking about Split part of Merge Sort Algorithm. In every Book Even in CLRS it is written that Dividing step take constant time and it is Big O(1). In my opinion it should be Big O(log n) Sep 26, 2016 at 18:21
• A single division step is done in constant time, but in aggregate for the entire algorithm, it's clearly `O(n)`. I'd have to look at the exact wording in the book, because that distinction is easy to mistake. Sep 26, 2016 at 18:31
• The exact line is this " The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = O(1)." Sep 26, 2016 at 20:01

If we assume that divide is an elementary operation and take very less time, then also we should include the time taken by divide

Big O doesn't actually measure how long a single operation takes. Rather, it measures how well an algorithm will scale as you increase the number of single operations.

Consider this graph: The horizonal axis represents n. The vertical axis represents the total computation time. Notice that, for small values of n, the O(n²) and O(n³) algorithms can actually perform better than their O(1) counterpart. That's because, in this hypothetical example, the single operation in the O(1) algorithm is more expensive than the single operations in the O(n²) and O(n³) algorithms.

I would consider "the dividing step takes constant time" to be rather obvious, but the reason it's constant time is because it is a single calculation.

At this point, all the author says is that a single divide step costs O(1). The author is not making a claim about doing 3 divide steps, or 1000000 divide steps.

• But while calculating time complexity we must take this into account Sep 27, 2016 at 15:22
• No, the author is not talking about the time complexity of N divide steps. The author is talking about the time complexity of 1 divide step. Just one. Sep 27, 2016 at 16:19
• but he wrote Exactly "D(n) = O(1).". Not D(1) Sep 27, 2016 at 16:22
• What does D(1) mean?
– user22815
Sep 27, 2016 at 16:27
• What is "D" ? I assume it means "Cost of a division"? If so, the author is talking about performing division on a number `n` just once. Not about dividing a number multiple times. Sep 27, 2016 at 16:29

The number of times to compare is the reason of time complexity for most sorting algorithms. In any divide and conquer algorithms, the maximum number of times to divide is n-1 which is smaller than nlog(n), thus it is negligible.