• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 225
  • 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
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
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
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.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

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