Ok, if you look at the inner loop, it is - for ( j = i to j = 0 ) { sum[j] += A[ i] product[j] *= A [ i] }
This is as good as executing - sum[i] = sum [ i ] + A[ i ] ---> ( 1 ) sum[i-1]= sum[i-1]+ A[i] ----> ( 2 ) ---------- ----------- ----------- sum[0] = sum[ 0]+A[i] ------> ( i ) Each of these assignments doesn't have any dependency with other computations i.e., ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , .... ( i ) and hence each of this can be assigned to a different processor. So, each of these statements( iterations) of the inner-loop j can be run in different processors, making it O(1). I am sorry, if people are still not getting my point !!! This is the best I can do !!! Kishen On Thu, Oct 21, 2010 at 9:08 AM, ligerdave <david.c...@gmail.com> wrote: > @Kishen > > I don't have much knowledge on parallel computation in OpenCL or CUDA. > Do you mean parallelised="not have to do the computation at all"? > did you mean without knowing the boundary of the inner loop which is > depended on the outer loop, the inner loop would be smart enough to > figure out the i and j? > > On Oct 20, 7:33 pm, Kishen Das <kishen....@gmail.com> wrote: > > Well, looks like people are not understanding when I say "run a loop in > > parallel "!!! > > > > Please look at some of the examples on Nvidia website on how computations > > can be parallelised in OpenCL or CUDA. > > And also some of the high level programming languages like Scala which is > > also providing these parallel constructs. > > > > If you don't understand GPUs or not familiar with parallel constructs in > > Java, then my algorithm will definitely look like O ( n ^ 2 ). > > > > Kishen > > > > > > > > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave <david.c...@gmail.com> wrote: > > > @Kishen > > > as long as you have one for loop in another, you wont have O(n). it > > > will most likely run O(n^2) > > > > > On Oct 19, 7:41 pm, Kishen Das <kishen....@gmail.com> wrote: > > > > In the below code the jth and kth inner for loops can be run in > parallel > > > > making them O(1) and the entire thing O(n). > > > > > > for ( i=0 to i=N-1 ) > > > > { > > > > > > for ( j = i to j = 0 ) { > > > > sum[j] += A[ i] > > > > product[j] *= A [ i] > > > > > > } > > > > > > for( k=0 to k= i ) > > > > if ( sum[k] == S and product[k] == P ) { > > > > Answer is the sub array A[k to i ] > > > > break > > > > > > } > > > > } > > > > > > Kishen > > > > > > On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh < > iiita2007...@gmail.com > > > >wrote: > > > > > > > @ Rahul patil ofcourse array may have negative or positive > integers > > > > > > > @ Kishen both O(n) and O(n logn) solutions was asked in this > yahoo > > > coding > > > > > round question > > > > > > > On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh < > > > > > iiita2007...@gmail.com> wrote: > > > > > > >> Given an array of length N. How will you find the minimum length > > > > >> contiguous sub - array of whose sum is S and whose product is P . > Here > > > > >> S and P will be given to you. > > > > > > >> -- > > > > >> You received this message because you are subscribed to the Google > > > Groups > > > > >> "Algorithm Geeks" group. > > > > >> To post to this group, send email to algoge...@googlegroups.com. > > > > >> To unsubscribe from this group, send email to > > > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups .com> > > > <algogeeks%2bunsubscr...@googlegroups .com> > > > > >> . > > > > >> For more options, visit this group at > > > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > > > -- > > > > > ABHISHEK KUMAR SINGH > > > > > BTECH (INFORMATION TECHNOLOGY) > > > > > IIIT ALLAHABAD > > > > > 9956640538 > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algoge...@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@googlegroups .com> > > > <algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > <algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.