Что значит O(1)?
Время работы алгоритма - константа. Т.е. не зависит от размера входных данных (или их нет вообще)
Тут - проще объяснить применительно к конкретным языкам разработки и технологиями. Например время доступа к элементу хеш таблицы Java (HashMap) оценивается как O(1). Тоесть время всегда постоянное и не зависит от прочих условия типа размера таблицы. А если у нас вместо хеш-таблицы - красно-черное дерево (TreeMap) - то тогда время доступа оценивается как O(log n). Тоесть логарифмически зависит от размера данных в дереве.

Считается что O(1) лучше чем O(log n). Но этот тезис действует на объеме данных близком к бесконечности. На малых объемах структуры - неразличимы или могут менять свои свойства в зависимости от разных начальных условий (были ли в кеше L1/L2/L3 до этого уже прочитанные данные).