@Lucifer
I am not getting how u r working with heapifying each time ..
Initially the array is such that minimum value is ay (0,0) and and max at
index (m-1,n-1)
Now when u swap a value
Then u heapify i.e. make the prior arrangement again but that in turn will
lead to few swaps and so on...(Recursive)
Do you think it will be possible this way ?
Please correct me in case I got things wrong here
regards
Ankur
On Wed, Jan 11, 2012 at 5:07 PM, atul anand <atul.87fri...@gmail.com> wrote:
> i have little doubt in complexity of proposed algo..
> aren't we including complexity of heapifying each time. ??
>
>
>
> On Wed, Jan 11, 2012 at 2:57 PM, Lucifer <sourabhd2...@gmail.com> wrote:
>
>> @dipit ..
>>
>> Yup you are correct..
>>
>> Say, no of rows = M and no. of cols = N,
>> Time complexity = sum over all i (1 to M} { N*(M+N-i) }
>> = M * N * (M + 2N - 1) /2
>>
>>
>>
>> On Jan 11, 2:19 pm, Dipit Grover <dipitgro...@gmail.com> wrote:
>> > @Lucifer : I came up with a similar algorithm as yours but I dont
>> > understand your complexity analysis : " sum over all i (1 to M} {
>> i*(M+N-i)} " .
>> >
>> > Shouldnt it be " M * sum over all i(1 to N) {(M+N-i)} " ? M= no of
>> > columns, N= no of rows . Since we always have the min element at the 0th
>> > column of the next row for each element of the current row.
>>
>> --
>> 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.
>> 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 algogeeks@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.
>
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
