2 ms·

Thanks for replying, I really appreciate you taking the time to check my concerns! I was afraid I was going crazy haha. The part about big O being usually abou

Thanks for replying, I really appreciate you taking the time to check my concerns! I was afraid I was going crazy haha. The part about big O being usually about the average case was helpful, I'm still at uni where we mostly talk about worst case performance.

vlovich123 2y ago
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).