Arunachalam wrote: > Please be complete with your question. Most of this group readers will not > be having the book. so please do explain whatever is stated about the > partial checking in that book. > > regards > Arunachalam. > > > On 7/2/06, Terry <[EMAIL PROTECTED]> wrote: > > > > > > hi, > > this is regarding a problem from programming pearls by jon bentley > > column 5. > > I have few questions , > > 1) how to check if an array is sorted or not. Can it be done it sub - > > linear time > > > > 2) In section 5.8 problem 5, he describes saying that checking a array > > is sorted or not takes n-1 operations. How can you add partial checking > > to the function at significantly less cost. > > > > I understand the n-1 part doing a > > for(i=0;i<n-1;i++) > > if(arr[i] > arr[i+1] > > return 0; > > > > but i don't get the partial checking part. > > > >
Well it says can you add partial checking or can you reduce the cost of checking a array is sorted to O(log n) or O(1) checking so that you can tell the array is sorted. We needn't completely check the array is sorted or not . We need partial checking. > > > > > > > > -- > =================================== > want to know more about me > http"//ww.livejournal.com/users/arunachalam > > ------=_Part_6205_27282247.1151908179624 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 1192 > > <div>Please be complete with your question. Most of this group readers will > not be having the book. so please do explain whatever is stated about the > partial checking in that book.</div> > <div> </div> > <div>regards</div> > <div>Arunachalam.<br><br> </div> > <div><span class="gmail_quote">On 7/2/06, <b > class="gmail_sendername">Terry</b> <<a href="mailto:[EMAIL > PROTECTED]">[EMAIL PROTECTED]</a>> wrote:</span> > <blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px > 0.8ex; BORDER-LEFT: #ccc 1px solid"><br>hi,<br>this is regarding a problem > from programming pearls by jon bentley<br>column 5.<br>I have few questions , > <br>1) how to check if an array is sorted or not. Can it be done > it sub -<br>linear time<br><br>2) In section 5.8 problem 5, he describes > saying that checking a array<br>is sorted or not takes n-1 > operations. How can you add partial checking > <br>to the function at significantly less cost.<br><br>I understand the n-1 > part doing a<br>for(i=0;i<n-1;i++)<br>if(arr[i] > arr[i+1]<br>return > 0;<br><br>but i don't get the partial checking > part.<br><br><br><br>http"//ww.livejournal.com/users/arunachalam > > ------=_Part_6205_27282247.1151908179624-- --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
