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

Solved

Posted on 2006-05-31

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;

}

// 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;

}

8 Comments

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.

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.

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

Just return the value of that counter from this function.

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

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)

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

Cross compile release version of c++ program for linux | 2 | 96 | |

Cell Value from TStringGrid::StringGrid1Dr |
3 | 43 | |

C++ to C# code conversion issue | 4 | 73 | |

Unable to start eclipse ? | 17 | 25 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**11** Experts available now in Live!