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

Question

Consider the following algorithm.

A).In plain English what is the algorithm f(v) doing? (as in sorting in ascending or descending order)

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

C).What is the worst case space complexity for the algorithm f(v)

void f(vector v){

Initialize A to be an empty AVL tree of integers Initialize

integer k to 0

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:

v[k] = the node’s data value

k = k + 1

Explanation / Answer

Steps in the algorithm:

A) The algorithm sorts the elements in the vector v in ascending 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:

v[k] = the node’s data value -> constant time
k = k + 1 -> constant time

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).

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 C
• Subjects

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