Complexity of a nested binary search tree

0
votes

Does anyone know how to calculate the complexity of a nested binary search tree? I have implemented a nested binary search tree to a depth of 3 BSTs.

EDIT: I apologize for the confusion, I had meant that each node of the BST would point to the root node of another BST. The complexity I was asking for was time complexity of search, update, and delete (basic operations). I had assume that since the time complexity of a BST was O(log(n)), the time complexity of a nested BST in terms of search, update, and delete wouldn't differ that much.

1
algorithmbinary-treebinary-search-tree
Complexity of what? Time complexity of some operation? – pajton
Define "complexity of a nested binary search tree". For that matter, define "nested binary search tree" (do you mean subtree?) – BlueRaja - Danny Pflughoeft
what do you mean by complexity? space? a particular operation? please expand – TimCodes.NET
I apologize for the confusion, I had meant that each node of the BST would point to the root node of another BST. The complexity I was asking for was time complexity of search, update, and delete (basic operations). I had assume that since the time complexity of a BST was O(log(n)), the time complexity of a nested BST in terms of search, update, and delete wouldn't differ that much. – Alberto Leal
"I had meant that each node of the BST would point to the root node of another BST." - That is the definition of a (single) BST :) – BlueRaja - Danny Pflughoeft

1 Answers

1
votes

I'm assuming that by "nested" you mean that each node of a particular tree points to the root of another tree, up to 3 levels deep.

Well a binary search tree is generally going to be O(log n) lookup time. Since you're doing 3 lookups, that's O(log a * log b * log c). Of course that's assuming that they're well balanced and everything. The worst case for a binary search tree is O(n) (think of a tree where it's basically a straight line). Then the worst case time would be O(a * b * c).

And for the record, a b and c are the number of elements in the first tree, second nested tree, and third doubly-nested tree, respectively.