• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 222
  • Last Modified:

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;
      temp = head;                  // set pointer to head of list
      while (temp != NULL)
      {
            temp = temp->next;      // follow the next pointer
            counter++;            // add one to our count
      }
      return counter;
    }
0
shingo43
Asked:
shingo43
  • 3
  • 2
  • 2
  • +1
1 Solution
 
rajeev_devinCommented:
I think this is of contant order. Since the number of elements is not fixed.
0
 
rajeev_devinCommented:
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
 
shingo43Author 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?
I am a little confued about counting algorithm orders,so please confirm.
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
brettmjohnsonCommented:
> 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
 
shingo43Author Commented:
OMG,then how do I change the method to make it O(1) time for counting,thanks
0
 
shingo43Author 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
 
brettmjohnsonCommented:
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
 
seet82Commented:
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

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 3
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now