Search code examples
algorithmsortingcomplexity-theory

With what ratio does the Divide and Conquer Algorithm stop being O(N * log(N))


The divide and conquer algorithm has a runtime complexity of O(N * log(N)) because it splits the problem into 2 smaller subproblems. Then the algorithm can be run again on the two smaller problems recursively until you find the solution which gives you a runtime of O(N * log(N)). This is the strategy that some sorting algorithms use to achieve above mentioned runtime. (They split the problem into two equally sized parts -> ratio 1/2 and 1/2)

So what are the limits to the ratios of this division? Is the runtime still O(N*log(N)) if you split the problem into 1/4 and 3/4 original size? What about 1/10 and 9/10 or less?


Solution

  • You can answer it precisely based on the Akra-Bazzi theorem. If we have T(n) = T(a*n) + T(b*n) + n such that a and b are positive constant, less than 1, and a + b = 1, then we can say T(n) will be in O(n log n).

    Hence, for a = 1/10 and b = 9/10, we can say the same as a = 1/2 and b = 1/2 or a = 1/4 and b = 3/4.