@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors are
running in parallel.
Buddy, with parallel processors you can reduce total computation time at
most by a factor of number of processors you have (which will always be a
constant, no matter how big it is). It has nothing to do with time
complexity.
Thanks,
- Ravindra
On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das <kishen....@gmail.com> wrote:
> 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<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.
