@hemanth: doing it in seperate for loops or in a single for loop both results in O(n) time.It does not make a difference.
I think there cannot be a solution better than O(n) as we need to traverse the array atleast once..... On Fri, Jul 1, 2011 at 12:57 PM, Hemanth Sagar <[email protected]>wrote: > The most efficient code will be surely of O(n). This is because there is no > way of finding > the min and max without scanning the entire array atleast once. > > Is this so? or any counter arguments ? > > > On Sat, Jul 2, 2011 at 1:06 AM, rajeevrvis <[email protected]>wrote: > >> Are there any Algorithms for finding efficient max differences ? >> >> >> On Jul 1, 11:42 pm, Hemanth 007 <[email protected]> wrote: >> > Hii, >> > One improvement is that finding min and max can be done in a single >> > run, rather than calling the findMin and findMax separately. >> > But yet the order is O(n); >> > Is there any better soln than O(n); >> > >> > #include<stdio.h> >> > #include<limits.h> >> > void findExtreme(int array[],int size,int* min,int* max){ >> > int i; >> > for(i=0;i<size;i++){ >> > if(array[i] > *max)*max = array[i]; >> > if(array[i]<*min)*min=array[i]; >> > } >> > >> > } >> > >> > main(){ >> > int arr[]={0,609,211,432,31,2222}; >> > int max=INT_MIN,min=INT_MAX; >> > findExtreme(arr,sizeof(arr)/sizeof(arr[0]),&min,&max); >> > printf("%d %d ",max,min); >> > printf("%d",max-min);} >> > >> > ~ >> > ~ >> > ~ >> >> -- >> 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. >> >> > -- > 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. > -- 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.
