O(1) and O(log n), are they same thing?

Question

There is a question asking whether taking a minimum element from a min-heap is o(logn) time, I thought it was false because it takes constant time because the minimum element is on the top. But the answer is true and the instructor's explanation is that constant time is also of O(logn), it was a wording issue. I am quite confused. So in practice, do we consider constant time a runtime of O(logn)?

Answer 1

It is true that anything that is O(1) is O(log n). However, it is not true that everything that is O(log n) is O(1). O is an upper bound, so you can always use a faster-growing function.

Think of it like this:

• Mickey Mouse is a mouse
• All mice are mammals
• Hence, Mickey Mouse is a mammal
• ... but "mice" and "mammals" are not synonymous