Compelxity of the two appraoches

#1

In first brute forces apporoaches we are iterate over each column and row and complexity is n^6 but in the prefix sum arrays we also use the two loops so what the difference in the complexity

#2

hello @Vikaspal

in brute force.
first we select top left corner of submatrix using two loops

then we select bottom right corner of submatrix using two loops
and then we find sum of this submatrix by running two loops.

so total 6 nested loops thats why time complexity is O(n^6)

now
in prefix approach.
first we select top left corner of submatrix using two loops

then we select bottom right corner of submatrix using two loops
and then we will use of prefix array to compute the sum in O(1)
so total 4 nested loops therefore time compelxity O(n^4)

#3

@aman212yadav the same we are using the two loops for computing the prefix sum array right+
so n^2 and n^4 + k for aritmetic operation right overall will n^4 …?

#4

yeah…

#5

how to use the two pointer to generate the sub-maxtix like we did in 1-d arrays

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.