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