0
    void reverseQueue(queue<int>& Queue)
    {
         stack<int> Stack;
         while (!Queue.empty())
         {
             Stack.push(Queue.front());
             Queue.pop();
         }
         while (!Stack.empty())
         {
             Queue.push(Stack.top());
             Stack.pop();
         }
    }

I was wondering what the Big-O or Big-Theta notation of this function would be, if we called it with a Queue of n elements. Would it be something along the lines of O(n^2), since we're pushing and popping n elements twice in order to move it from the stack back to the queue in a reversed order? Thank you for any help.

smith1453
  • 151
  • 1
  • 1
  • 6
  • 2
    What happens when you double the number of elements? Try on paper (or on your fingers) with five elements, then with ten. What happens to the number of operations? Does it quadruple? – Beta May 11 '18 at 00:02

1 Answers1

1

The Big O for this function is O(n) because your traversing the queue only twice. Theoretically this is also true if you do it K times, where K is a constant and it dose not change with the queue size n. O(n^2) is when, for example, you have a loop inside of another and so you are traversing the queue n*n times.

You can also check: Which algorithm is faster O(N) or O(2N)?

scrapper
  • 361
  • 2
  • 6