A).Consider the following algorithm. In plain English what is the algorithm g(v)
ID: 3814942 • Letter: A
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).