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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <
> [email protected]
> > > >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 <
> > > > > [email protected]> 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 [email protected].
> > > > >> To unsubscribe from this group, send email to
> > > > >> [email protected]<algogeeks%[email protected]>
> <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 [email protected].
> > > > > To unsubscribe from this group, send email to
> > > > > [email protected]<algogeeks%[email protected]>
> <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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%[email protected]>
> <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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[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.
