Question

1. Suppose you have three stacks. Stack source is full of random data and stacks aux and dest are empty To sort the data in the source, you can repeatedly remove the largest value by popping each item off of source and pushing it onto aux, remembering the maximum value seen as you empty source. When source is empty, you pop each item off of aux and push it back onto source except for the largest one that you remembered, which you push to dest instead. If you repeat this process until both source and aux are empty, then you can pop the contents of dest in increasing order, successfully sorting the contents of the original stack.

   What is the worst-case performance of stacksort?

   O(n^3)
2. O(n^2)
3. O(n/2)
4. O(n)
5. O(2n)
6. O(2^n)

Answer 1

Answer :

O(n^2)

Explanation : The worst-case performance of stacksort is O(n^2).

As we have three stacks here, if the elements of the stack source are in sorted order, then the performance will be O(2n). Here, the elements are in random order, so in worst case, the performance will be O(n^2).

For each element to be placed in the sorting order, maximum it will take n operations. So, in worst case, n elements will take n operations each. So, the total operations will be n*n=n^2.

Therefore, the worst-case performance of stacksort is O(n^2).