Asymptotic complexity can never be better than O(n). But you can reduce the number of exact comparisons from 2n to 3n/2 . Take pair of numbers in each iteration and compare them. Then compare the smaller to Min and greater to Max . This way, you have 3 comparisons for every iteration where the number of iterations is n/2 so total number of comparison is 3n/2.
On Jul 2, 8:47 am, Hemanth Sagar <[email protected]> wrote: > @sameer > Though the asymptotic time complexity is equal,i.e. O(n), the actual time > complexity is also influenced by the constants. I claim that running two > loops will be slower because there are now three operations that are to be > done additionally than the single loop. > > Also, if you take the case of insertion sort (vs) merge sort, though the > time complexity of merge sort (nlogn) is better than insertion sort(n^2), > for small n values, insertion sort is better. This is because there is also > a role played by the constants. > > Correct me if I am wrong ! > > - > Hemanth > > On Sat, Jul 2, 2011 at 8:20 AM, [email protected] < > > [email protected]> wrote: > > @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. -- 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.
