yes upto the step of swapping the elements it is O(m+n) but if you need final arrays also sorted (Seems like that from your first post)....it will go nlgn
On Fri, Jul 8, 2011 at 1:25 AM, radha krishnan <[email protected] > wrote: > ok ! i got a O(n lgn) finally > i don know exact complexity > Let N = size of first array > Find the first N smallest elements using one pointer in each array > now swap the list of elements from index 0 to second-pointer in > second array to first array > with first_poiner+1 to N in first Array > I think this is O(n) > > On Thu, Jul 7, 2011 at 12:53 PM, Piyush Sinha <[email protected]> > wrote: > > @radha...i have an algo but its complexity is O(n^2)...check the > > following and see if there is any bug as I havent tested for all > > cases...also suggestions are welcomed....:) > > > > main() > > { > > int a[]= {1,3,77,78,88}; > > int b[]= {2,5,79,80,81,99}; > > int i=sizeof(a)/sizeof(a[0]) - 1; > > int j=sizeof(b)/sizeof(b[0]) - 1; > > int temp,k,m; > > while(j>=0) > > { > > if(a[i]>b[j]) > > { > > temp = a[i]; > > k=m=i; > > while(b[j]<a[k-1]) k--; > > while(i-k) > > { > > a[i] = a[i-1]; > > i--; > > } > > a[i] = b[j]; > > b[j] = temp; > > i = m; > > } > > j--; > > } > > for(k=0;k<sizeof(a)/sizeof(a[0]);k++) > > printf("%d ",a[k]); > > puts("\n"); > > for(k=0;k<sizeof(b)/sizeof(b[0]);k++) > > printf("%d ",b[k]); > > puts("\n"); > > system("pause"); > > } > > > > > > On 7/8/11, radha krishnan <[email protected]> wrote: > >> :Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge > >> these two arrays, no extra spaces are allowed. Output has to be > >> a[]={1,2,3,5,77} and b[]={78,79,81,90}. > >> > >> -- > >> 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. > >> > >> > > > > > > -- > > *Piyush Sinha* > > *IIIT, Allahabad* > > *+91-8792136657* > > *+91-7483122727* > > *https://www.facebook.com/profile.php?id=100000655377926 * > > > > -- > > 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. > > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
