@ravindra agree!
On Oct 24, 2:20 pm, ravindra patel <[email protected]> wrote: > @ 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 <[email protected]> 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 <[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%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 [email protected]. > >> > > > > To unsubscribe from this group, send email to > >> > > > > [email protected]<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 [email protected]. > >> > > To unsubscribe from this group, send email to > >> > > [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%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%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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
