The tim The time to search for a value in a tree hinges on the depth of the tree

Question

The tim

The time to search for a value in a tree hinges on the depth of the tree. Imagine that a tree supports operations of add element, and remove specific element. (That is, if a specific element is not found, the tree is returned with the same amount of nodes.) Beginning with a balanced tree, as elements are added/removed, such a tree can become unbalanced. Now imagine a tree could be kept balanced for a cost of 1 unit per add, plus 1 per remove operation. Compare the computational complexity of n adds and n removes (of specific elements, not necessarily found) in a tree that maintains balance, and one that does not. Describe your reasoning making use of Big-O notation.

Explanation / Answer

Worst case analysis :

tree is balanced and has x elements:

add takes O(log x) as depth becomes logx;

So, n adds and n removes takes n*O(log x) + n* O(log x)

=2nO(log x);

=O(log x); (similar according to Big _O notation)

Tree is imbalanced

add takes O( x) as depth becomes x in worst case;

So, n adds and n removes takes n*O(x) + n* O(l x)

=2nO(x);

=O(x); (similar according to Big _O notation)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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