A).Consider the following algorithm. In plain English what is the algorithm g(v)

Question

A).Consider the following algorithm. In plain English what is the algorithm g(v)doing?

Also B). What is the worst case time complexity for the algorithm g(v)

void g(vector v){

Initialize A to be an empty AVL tree of integers

Initialize integer k to be 0

Initialize S to be an empty stack of integers

For each value i in v, insert i into A

Do an in-order traversal of A, and when visiting each node do the following: S.push(the node’s data value)

While S is not empty, do the following:

v[k] = S.top()

S.pop()

k = k + 1 }

Explanation / Answer

Steps in the algorithm:

A) The algorithm sorts the elements in the vector v in descending order.

1) For each value i in v, insert i into A.

This step takes O(nlogn) time. (n being the number of values in v). Inserting into an AVL tree takes O(logn) time and we should do it n times, so the total time taken is O(nlogn).

2) Do an in-order traversal of A, and when visiting each node do the following: S.push(the node’s data value)

For doing an in-order traversal we visit all the nodes in the tree. The number of nodes is n, so the total time taken for all this is O(n).

3) While S is not empty, do the following:
v[k] = S.top() -> constant time
S.pop() -> constant time
k = k + 1 -> constant time

We pop all the elements in the stack. As there are n values in the stack. The time taken is O(n).

The space taken by the tree is O(n). As there are n nodes in the tree.

B) So the total time taken in worst case is O(nlogn)

C) The worst case space complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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