When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n).
The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave <[email protected]> wrote: > > When you say that checking if any of the ancestors is O(n log n) are > you assuming that the tree is balanced? It wouldn't be O(n log n) if > the tree degenerates into a linked list, would it? So what is your > justification in assuming balance? > > Dave > > On Aug 30, 6:01 pm, Ramaswamy R <[email protected]> wrote: > > To begin with I find the invariant doesn't hold in the system > progressively. > > Forget about islock and assume that we only do lock / unlock. Given that > a > > node cannot be locked if any of its descendants / ancestors is locked. It > is > > never possible for the tree to enter a state where any of the descendant > of > > a locked node is locked. > > > > If that invariant holds then all we need to check is if any of the > ancestors > > are locked, which is O(log n). O(1) would either require hash table (and > > O(n) storage) unless we choose to replicate the lock state in all of the > > ancestors as well (which is a pretty ugly solution considering what > unlock > > would have to do). > > > > If we can supplement the tree node with a lock status and pointer to > child > > (only used while unlocking) which is locked we should be able to do it > all > > in the asked for complexities :). Ugly but possible. Of course there is > an > > O(n) extra storage. > > > > On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar <[email protected] > >wrote: > > > > > > > > > > > > > > > > > Given a n-ary tree of resources arranged hierarchically. A process > > > needs to lock a resource node in order to use it. But, > > > A node cannot be locked if any of its descendant or ancestor is > > > locked. > > > I was supposed to > > > -> write the structure of node > > > -> write codes for > > > -> islock()- returns true if a given node is locked and false if it is > > > not > > > -> lock()- locks the given node if possible and updates lock > > > information > > > -> unlock()- unlocks the node and updates information. > > > Codes should be : > > > Islock –O(1) > > > Lock()- O(log n) > > > unLock()- O(log n) > > > > -- > > Yesterday is History. > > Tomorrow is a Mystery. > > Today is a Gift! That is why it is called the Present :). > > > > http://sites.google.com/site/ramaswamyr- Hide quoted text - > > > > - Show quoted text - > > > -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
