wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Skiena Find-Minimum(Q) in O(1) - How?
        
(Message started by: Ved on Aug 28th, 2011, 7:58am)
Title: Skiena Find-Minimum(Q) in O(1) - How?
Post by Ved on Aug 28th, 2011, 7:58am
Skiena's 'Algorithm Design Manual' (2nd Ed.) Page: 85 has the following : "The unsorted array dictionary implemented insertion and deletion on constant time and search and minimum in linear time"...after this there is a table that shows :

                                       Unsorted Array     Sorted Array     Balanced Tree
Find-Minimum(Q)              O(1)               O(1)             O(log n)

Unsorted array O(1) for findinng minimum seems wrong to me (and contradicts the earlier statement on the same page)

Is this is an unreported erratum ?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board