It's also only O(log n) if the scene is static. Which is what is often missed in the quest for more photo-realistic graphics - it doesn't mean anything if what you are rendering only looks realistic in still frames but doesn't behave realistically if you try to interact with it.

What if we keep the number of triangles constant per pixel, independently of scene complexity, through something like virtualized geometry? Though this would then require rebuilding part of the BVH each frame, even for static scenes, which is probably not a constant operation.

For static geometry we could but for animated geometry or dynamic geometry it would have to be calculated during a mesh shader step.