@Rohit: Doesn't init also have to initialize all of the Validity fields to something <= the value of maxcount, which is O(n)? If not, how can you be certain that the uninitialized unspecified (random) values in the Validity fields are not > maxcount?
Dave On Nov 1, 2:06 am, Rohit Saraf <[email protected]> wrote: > datastructure > Validity - integer > Value - Whatever > > Make an array of the above datastruct (say d[n+1] starting from 1) > integer maxcount > > Init(val) > d[n+1].Value = val > d[n+1].Validity = ++maxcount > > Set(i,x) > d[i].Value=x > d[i].Validity = d[n+1].Validity+1 > > Get(i) > if( d[i].Validity <= d[n+1].Validity ) then d[n+1].Value > else d[i].Value > > There is a practical issue that Validity may become larger than int etc... > however that too can be easily overcome. > > -------------------------------------------------- > Rohit Saraf > Third Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- 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?hl=en.
