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
Code: Select all
for(i=0;i<n-1;i++)
if(arr[i] > arr[i+1]
return 0;