Rama, I cannot agree with you more here. On Aug 31, 5:34 am, Ramaswamy R <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
