Complexity of a nested binary search tree

Question

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.

Define "complexity of a nested binary search tree". For that matter, define "nested binary search tree" (do you mean subtree?) — BlueRaja - Danny Pflughoeft
– BlueRaja - Danny Pflughoeft, Commented Apr 6, 2011 at 20:24
what do you mean by complexity? space? a particular operation? please expand — TimCodes.NET
– TimCodes.NET, Commented Apr 6, 2011 at 20:24
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
– Alberto Leal, Commented Apr 6, 2011 at 23:13
"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
– BlueRaja - Danny Pflughoeft, Commented Apr 7, 2011 at 4:12

Chris Eberle · Accepted Answer · 2011-04-06 20:26:43Z

1

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.

answered Apr 6, 2011 at 20:26

Chris Eberle

48.9k12 gold badges85 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Ted Hopp Over a year ago

Why did this earn a downvote? Given the vagueness of the question, this is as reasonable a guess at what OP was after as anything.

Chris Eberle Over a year ago

Thanks, @Ted Hopp. I stated my assumption, if you don't agree then simply don't accept it.

BlueRaja - Danny Pflughoeft Over a year ago

@Ted @Chris: Because it's actually O(log a + log b + log c) = O(log(abc)), which is the depth you'd get by treating the multiple "nested" trees as one big tree. Which makes sense, because all nodes in any tree are themselves nested trees, by definition. It is this property which makes recursion so useful when dealing with trees.

Chris Eberle Over a year ago

@BlueRaja: You are correct! Yes after all it's not like each subtree is being called by each node on the way down, is it? I was thinking in terms of loops. Good call.

Alberto Leal Over a year ago

I had originally thought that the time complexity would be O(log a * log b * log c), but I wasn't sure if this was correct. I think BlueRaja's answer would make more sense.

|

Collectives™ on Stack Overflow

Complexity of a nested binary search tree

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related