Suppose you are given an array A containing n numbers in ord

Suppose you are given an array, A, containing n numbers in order. Describe in pseudocode an efcient algorithm for reversing the order of the numbers in A using a singlefor-loop that indexes through the cells of A, to insert each element into a stack, and then another for-loop that removes the elements from the stack and puts them back into A in reverse order. What is the running time of this algorithm?

Solution

1.) for i = 0 to (A.length-1)

2.) push (A[i])

3.) for i = 0 to (A.length-1)

4.) A[i] = pop()

Running time of the algorithm:

Push and pop operation takes O(1). So,running time of this algorithm will be O(n) + O(n) = O(n)