Does the following function sort v in ascending or decending order? Also, what i

Question

Does the following function sort v in ascending or decending order? Also, what is the worst case time complexity for function(v) assuming that a single stack operation runs in constant time?

void function(vector v){

Initialize T to be an empty AVL tree of ints n=0

Initialize S to be an empty stack of integers

For each value i in v, insert i into T

Do an in-order traversal of T, and when visiting each node do the following:

(S.push(node’s data value))

While S not empty, do the following:

( v[n] = S.top()

S.pop()

n = n + 1)

}

Explanation / Answer

The algorithm has three main steps:

1) Push all the numbers in to an AVL tree
2) Do an inorder traversal and push all the numbers on to stack
3) Pop all the numbers from stack

In step 2, as we are doing an inorder traversal. We read the numbers in ascending order. We push them to the stack.

But in step 3 as we popping them from the stack. We are printing them in the descending order.

The time taken for step 1 is O(nlogn), this will be same even in the worst case as it is an AVL tree.

The time taken for steps 2 and 3 are O(n).

So the total time taken is O(nlogn), even in the worst case.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.