0
$\begingroup$

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 ?

$\endgroup$
4
$\begingroup$

If you're talking about an ADT, you can't really say. It depends on the implementation. You can certainly do it in O(1) (for example by keeping a counter).

$\endgroup$
2
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.