What is the time complexity for getting the size of a heap?

Assuming the regular Heap ADT.

What is the time complexity of getting its size ?

I tend to think that because insert is O(log(n)), then I always know the last index of my heap. So in order to get its size all I need is to return the last index + 1.

However I have seen in some places that refer to the size of the heap's complexity as O(n), since I need to count all the nodes in my heap.

Why am I wrong ?

Depends on how you implement your ADT heap. You can expand size as a counter of next operations. In that manner, if you are using

• an external counter: $O(1)$

• a stack: $O(n)$

• a binary tree: $O(logn)$

• a hash: $O(k)$ ($k$ is the average collisions)

StackExchange Computer Science Q#69581, answer score: 4