@All...
Infact if we closely observe, then for A[row][col] when replaced with
A[row+1][0].. Then on heapifying the matrix rooted at A[row+1][0], the
new value will have shifts within the submatrix (A[row+1][0] , A[M]
[col])
Hence, the actual time complexity would be :
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M}
{
sum over all j (1 to N}
{
(M - i + j)
}
}
= M*N*(M + N)/2
On Jan 11, 2:27 pm, Lucifer <[email protected]> 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 <[email protected]> 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 [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.
