Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1).

Ex: Binary heap.

Basic action is:

  1. Compare 2 childen.
  2. Compare the "winner" with his parent.
  3. Replace when needed.
  4. Do 1-3 with the "winner", until and including the root.

How is O(1) even possible?

share|improve this question

closed as unclear what you're asking by Juho, vonbrand, David Richerby, FrankW, jbapple Feb 27 at 5:50

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
Maybe you should ask him/her to clarify what was meant exactly. What "basic action"? Data structures you will encounter where? –  Juho Feb 24 at 18:20
    
Did you look at Wikipedia, Binary heap? –  J.-E. Pin Feb 25 at 11:22
add comment

2 Answers 2

up vote 5 down vote accepted

What was meant is that every data structure is designed to do something really well, e.g:

  • For an array, lookup by index is O(1)
  • For a linked list, insertion at the head is O(1)
  • For a heap, finding the smallest element is O(1)

... and so on. This doesn't mean that the operation that is O(1) for one data structure wouldn't have much worse complexity for some other data structure.

share|improve this answer
add comment

After EDIT in Question:

The operations in step 1, 2 and 3, you mentioned, are actually O(1).

By O(1) it is not meant that it is going to take 1 step only but it means that whatever time it is taking is CONSTANT. That constant can be small or large, but as you increase number of nodes in your tree, these basic operations are not going to take more time. Be it on a tree with 3 nodes or 200 nodes, one of these operation is going to take the same amount of time each time.

For an example, take operation 1 Compare 2 children. It is always going to take same number of comparison(here 1).

But if you say the sequence of step 1, 2, 3, 4 in order, as an algorithm. Then it is not O(1) and instead O(log n) with n being the number of nodes in the tree. Reason being, the operation 1-3 are done from a bottom pair of two nodes, propagating to top root node. So, in worst case it will traverse equal to height of the tree which is log n.

share|improve this answer
add comment

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