[algogeeks] Re: Test Cases
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 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, sameer.mut...@gmail.com <
>
> sameer.mut...@gmail.com> 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 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
> >> wrote:
>
> >>> Are there any Algorithms for finding efficient max differences ?
>
> >>> On Jul 1, 11:42 pm, Hemanth 007 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
> >>> > #include
> >>> > void findExtreme(int array[],int size,int* min,int* max){
> >>> > int i;
> >>> > for(i=0;i >>> > if(array[i] > *max)*max = array[i];
> >>> > if(array[i]<*min)*min=array[i];
> >>> > }
>
> >>> > }
>
> >>> > main(){
> >>> > int arr[]={0,609,211,432,31,};
> >>> > 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 algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> 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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Test Cases
@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, sameer.mut...@gmail.com <
sameer.mut...@gmail.com> 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 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 wrote:
>>
>>> Are there any Algorithms for finding efficient max differences ?
>>>
>>>
>>> On Jul 1, 11:42 pm, Hemanth 007 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
>>> > #include
>>> > void findExtreme(int array[],int size,int* min,int* max){
>>> > int i;
>>> > for(i=0;i>> > if(array[i] > *max)*max = array[i];
>>> > if(array[i]<*min)*min=array[i];
>>> > }
>>> >
>>> > }
>>> >
>>> > main(){
>>> > int arr[]={0,609,211,432,31,};
>>> > 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Test Cases
@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 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 wrote:
>
>> Are there any Algorithms for finding efficient max differences ?
>>
>>
>> On Jul 1, 11:42 pm, Hemanth 007 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
>> > #include
>> > void findExtreme(int array[],int size,int* min,int* max){
>> > int i;
>> > for(i=0;i> > if(array[i] > *max)*max = array[i];
>> > if(array[i]<*min)*min=array[i];
>> > }
>> >
>> > }
>> >
>> > main(){
>> > int arr[]={0,609,211,432,31,};
>> > 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Test Cases
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 wrote:
> Are there any Algorithms for finding efficient max differences ?
>
>
> On Jul 1, 11:42 pm, Hemanth 007 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
> > #include
> > void findExtreme(int array[],int size,int* min,int* max){
> > int i;
> > for(i=0;i > if(array[i] > *max)*max = array[i];
> > if(array[i]<*min)*min=array[i];
> > }
> >
> > }
> >
> > main(){
> > int arr[]={0,609,211,432,31,};
> > 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Test Cases
Are there any Algorithms for finding efficient max differences ?
On Jul 1, 11:42 pm, Hemanth 007 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
> #include
> void findExtreme(int array[],int size,int* min,int* max){
> int i;
> for(i=0;i if(array[i] > *max)*max = array[i];
> if(array[i]<*min)*min=array[i];
> }
>
> }
>
> main(){
> int arr[]={0,609,211,432,31,};
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Test Cases
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
#include
void findExtreme(int array[],int size,int* min,int* max){
int i;
for(i=0;i *max)*max = array[i];
if(array[i]<*min)*min=array[i];
}
}
main(){
int arr[]={0,609,211,432,31,};
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Test Cases
I would add that you should test all combinations of positive and negative operands. You are not clear about the type being divided. If it is a floating point type, you can verify that (a*b) / b = a to an acceptable tolerance for a wide variety of values of a and b. If you are working with integers, the case 4 below is good, given r < b. Don On May 10, 11:12 am, Praveen Kumar wrote: > cases would be: > 1. division by 0 raises an appropriate Exception > 2. dividing 0 by any number should result in 0 > 3. dividing any number by 1 should give the same number > 4. a = b*q + r i.e a/b should give q > > On Tue, May 10, 2011 at 7:52 PM, Carl Barton > wrote: > > > Don't really get the question > > > On 10 May 2011 09:08, Akshata Sharma wrote: > > >> write test cases for the division '/' operator.. > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algogeeks@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com. > >> 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 algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
