• Status: Solved
• Priority: Medium
• Security: Public
• Views: 225

# how to change the code so that it takes O(1) times

int Queue::getLength() const
// preconditions:      none
// postconditions:      return the number of elements in the queue
{
int counter = 0;            // variable will count items in queue
NodePointer temp;
while (temp != NULL)
{
temp = temp->next;      // follow the next pointer
counter++;            // add one to our count
}
return counter;
}
0
shingo43
• 3
• 2
• 2
• +1
1 Solution

Commented:
I think this is of contant order. Since the number of elements is not fixed.
0

Commented:
If you want to do something like this

int Queue::getLength() const {
return (m_TotalElements);
}

then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.
0

Author Commented:
then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.

just to verify that,in the above way,it takes O(1) right?
like if I enquese 5 times and use counter++,it will return 5 and only takes O(1) times? not 5 times?
0

Commented:
> just to verify that,in the above way,it takes O(1) right?

No the above code is of order O(n), where n is the number of items in the list.
[OK, it is O(1) if there is 1 item in the list.]
0

Author Commented:
OMG,then how do I change the method to make it O(1) time for counting,thanks
0

Author Commented:
then increment this counter when you insert a element in the queue, and decrement when you remove it.
Just return the value of that counter from this function.

Is this method right or wrong for the question requirement??thanks
0

Commented:
You answered your own question.  The only way to make it O(1) is to maintain the count of items in the list as you go.  Returning the precalculated count would be O(1).  This is useful if you modify the list infreqently, but ask it's count a whole lot.  If, however, you add [and remove] item to the list frequently, but rarely ask how many are on the queue, then the O(n) solution is probably more appropriate.
0

Commented:
O(n) => the time complexity for the function depends linearly with the number of items in question
O(1) => the time complexity for the function is constant and does not depends on the number of items in questiong

for your implementation, you need to loop through the list as many times as the number of items(n) and thus it is in O(n)

for the counter implementation, you will only need to return the counter which makes it O(1)
it does not matters if you enqueue 5 times as enqueue is another function.

O(5) is equivalent to O(1) and normally, nobody talks in term of O(5) but only O(1)
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.