I am solving Segment tree and Quad Tree related problems; while I noticed that in segment tree we split the 1D array into 2 (2^1) segments and recursively do this until base case arrives. Similarly, in Quad tree We subdivide the 2D grid into 4 (2^2) segments in every step. All these divide-and-Conquer mechanism is for achieving logarithmic time complexity. No offense!
But why don't we subdivide the array into 4 (4^1) parts or more instead of 2 parts in segment tree? And why we don't split the grid into 16 (4^2) parts instead of 4? By doing these, We can achieve O(log(N)) performance, but it would be a better log as log(N)(base 4) is better than log(N)(base 2).
I know in this case, the implementation would be little bit difficult. Is there a memory overhead problem? Or anything?
Please correct me if I am wrong anywhere. Thanks!
It wouldn't actually work faster. Let's assume that we divided it into 4 parts. Then we would have to merge 4 values instead of 2 in each node to answer the query. Assuming that merging 4 values takes 3 times longer(for example, to get the maximum of 2 numbers we need 1 call to max function, but to get the maximum of 4 values 3 calls are required), we have log4(n) * 3 > log2(n) * 1. Moreover, it would be harder to implement(more cases to be considered and so on).