educative.io

Full table scan should be O(n), why Log2(N)?

If we go through each of the elements in all the table, where does Log comes from? We don’t have index or something like this for that.


Course: Deep Dive into the Internals of the Database - Learn Interactively
Lesson: What Is a Database Index?

Hi @Dmitry_Polovinkin,
Thanks for pointing this out. Yes, you are right. The sequential scan should be O(n). It was mistakenly written. The changes have been made to the lesson.

Happy Learning!

1 Like