Asymptotic Analysis of Reversing a Queue

Question

    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.

Answer 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)?