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)