I was given this as a homework exercise, yet I don't know whether my solution is sound:
Given a complete binary search tree where blocks are formed in order of the value of the nodes. What would the amount of IOs be to reach any leaf from the root?
I think I can define the amount of IOs recursively as follows:
search(A) = search(A/2)+1 if n>B/2 = 0 otherwise
Where n is the size of A and B is the block size.
Since I think storing in order would always store a complete subtree of size B/2 in the same block.
This would then give log2(2n/B) IO operations for any root to leaf traversal.
Firstly, is that a correct bound? Secondly, is the storing of a complete B/2 sized subtree guaranteed with block size B?
Note that the bound is for amount of IO operations, not time complexity.