2

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????

Improve this question
5
  • 1
    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)
    – Bhaskar
    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.
    – Ordous
    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
    – Bhaskar
    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.
    – Kristian H
    Oct 17, 2016 at 9:30

4 Answers 4

Reset to default
1

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.

Improve this answer
3
  • 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)
    – Bhaskar
    Sep 26, 2016 at 18:21
  • 1
    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.
    – Karl Bielefeldt
    Sep 26, 2016 at 18:31
  • 1
    The exact line is this " The divide step just computes the middle of the subarray, which takes constant time. Thus, D(n) = O(1)."
    – Bhaskar
    Sep 26, 2016 at 20:01
2

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:

enter image description here

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.

Improve this answer
0

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.

Improve this answer
5
  • But while calculating time complexity we must take this into account
    – Bhaskar
    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.
    – Rufflewind
    Sep 27, 2016 at 16:19
  • but he wrote Exactly "D(n) = O(1).". Not D(1)
    – Bhaskar
    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.
    – Rufflewind
    Sep 27, 2016 at 16:29
0

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.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.