@Ravindra, Ligerdave You guys are all right. But with GPUs, you can literally have thousands of threads running in parallel. Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a single processor system. It was more towards making the members of this group to think on the lines of Parallelism. I long back agreed that the worst case for my algorithm is O(n^2 ) on single processor systems.
The current problem is a variation of original subset problem which is NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem ) I really appreciate a O(n) solution to this problem on a single-processor system. Kishen On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel <[email protected]>wrote: > >> It has nothing to do with time complexity. > My bad. Wrong choice of words. So in the PRAM model you can say the time > complexity is O(1), a pure theoretical concept. But the cost still remains > O(n), isn't it. > > I guess now onwards we'll have to specifically ask interviewers whether > they are asking for time complexity on scalar machine or on a parallel > machine. Unless specified otherwise, my assumption by default would be a > scalar one though. > > - Ravindra > > > On Sun, Oct 24, 2010 at 11:50 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%[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]<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]<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.
