• Some users have recently had their accounts hijacked. It seems that the now defunct EVGA forums might have compromised your password there and seems many are using the same PW here. We would suggest you UPDATE YOUR PASSWORD and TURN ON 2FA for your account here to further secure it. None of the compromised accounts had 2FA turned on.
    Once you have enabled 2FA, your account will be updated soon to show a badge, letting other members know that you use 2FA to protect your account. This should be beneficial for everyone that uses FSFT.

searching a tree

E

eon

2[H]4U
Joined
Oct 11, 2003
Messages
2,218
given that you know the worst case time of searching the entire tree and the number of solutions, is there a way to approximate the time to find just a single solution from the tree?
 
I would think that depends on whether the tree is balanced, and what kind of implementation it is (red/black, 2/3/4, BTree, etc)

In a normal binary search tree i believe it's something like O(log N) best case ( O(n) in the worst)
 
KaosDG said:
I would think that depends on whether the tree is balanced, and what kind of implementation it is (red/black, 2/3/4, BTree, etc)

In a normal binary search tree i believe it's something like O(log N) best case ( O(n) in the worst)
Click to expand...

Best case is O(1) (root node) worst case is O(n) (degenerate tree). Average case is O(log N)
 
i think kaos is right, you cant really make an approximation with making an assumption about the type/implementation of the tree. some implementations might always be O(logn) on the average, others O(n) (my "tree" implementation could simply be a linked list)
 
Hm, I'm thinking that he's not dealing with big-o notation.

But the point that you have to know the implementation of the tree still stands. Not every tree has a branching factor of 2, different tree structures have different worst-case characteristics (red-black for example has a worst case of 2log(n) while a simple binary tree is straight up n), and you'll even find trees with non-constant branching factors.

There's almost always a way to approximate an answer. The real question is how accurate of an approximation do you want? Simply saying the average case is the worst case / 2 would be an approximation. But probably not the most accurate that you could come up with.
 
What do you mean by "number of solutions, eon?
 
devman said:
Best case is O(1) (root node) worst case is O(n) (degenerate tree). Average case is O(log N)
Click to expand...


woops :) I did mean average case. But in "the Law of KaosDG is doing the coding", whatever you are searching for is never the root node :(


Khanmots said:
Hm, I'm thinking that he's not dealing with big-o notation.
Click to expand...
But what is big O but an approximation of how an algorithm will run? (either approximating runtime or memory usage, or some other resource)

If he has a fixed number of elements, and is looking for a numeric approximation - that number could always be generalized, and a given Big O representation of that approximation would generally hold true for any number of elements. (Big O is not exact, it's just meant to show what the major limiting factor is)
 
KaosDG said:
But what is big O but an approximation of how an algorithm will run? (either approximating runtime or memory usage, or some other resource)
Click to expand...

Wasn't trying to say that Big O notation wasn't appropriate... was simply trying to say that I don't think he knows what it is.
 
Khanmots said:
Wasn't trying to say that Big O notation wasn't appropriate... was simply trying to say that I don't think he knows what it is.
Click to expand...

true... but if this is a homework question, it's inevitably leading to Big-O :eek:
 
You must log in or register to reply here.
Back
Top