@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.
