I'll note I could very well be wrong - very back of the paper first principles derivation and could easily have made a mistake. If you're in a relevant course,

I'll note I could very well be wrong - very back of the paper first principles derivation and could easily have made a mistake. If you're in a relevant course, might be a good opportunity to flag this to a professor or TA as a way to review. These kind of analyses can be tricky sometimes, especially if you need to prove it vs just do an answer by feel which is how engineers end up doing it (vs CS students that take the proofs much more seriously). A way to sometimes double-check is to just simulate performance as input grows and see if it matches the expected log(N).