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

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)