0

The question is

If we’re storing a queue of integers using a vector (not a list) you may store items in such a way that the front of the queue is not necessarily at the zero position. If using this technique, what would be the Big-Theta runtime of the clear function? a. Theta(1) b. Theta(N) c. Theta(N* log(N) ) d. Theta(N^2)

Coursehero and Chegg and ChatGPT all say it should be Theta(N) because we need to iterate through all elements.

Bard says it should Theta(1).

I agree with bard, because why do we care where the front is if we're clearing everything? Can't we just release the memory and reset count to 0 since we're using an array based data structure?

Thanks!

Zhou Fang
  • 23
  • 3
  • 1
    That depends on what "the" clear function does, or is allowed to do. Often, data structures have a clear function that clears itself, to make it able to be reused, without freeing or allocating more memory. This is useful for guaranteeing efficient memory use. But yes, you CAN implement it in *O(1)* the way you suggest. – Berthur Mar 30 '23 at 21:28

0 Answers0