Search code examples
algorithmmergesortproof

3-way and 2-way merge sort without loss of generality?

So, I am studying 3-way merge sort and I am wondering about the without loss of generality.

lets assume that we have array A' with power of 3 elements and A with power of any constant.

Here is my question.

  1. Why having an assumption that n(number of elements) is a power of three is without loss of generality?

  2. WHy any assumption of the form that n is a power of a constant is also without loss of generality?

Solution

  • Because you can always enlarge an array A to fit the size that you want just for making an algorithm to work.

    An actual implementation might or might not use that assumption, but in principle taking the assumption does not prevent you to apply the algorithm to any array A of any size. The assumption about size is there because it simplifies the algorithm and is convenient for analyzing time and conplexity.