Comment by russfink

… yes to the 2^k only because if not met, the performance devolves to a linear search. By themselves, k-d trees can handle any number of records.