>> 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
<ravindra.it...@gmail.com>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 <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 algogeeks@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.
