if we do brute force method for 1 query we get time complexity O(mn) since we have to iterate over each element, and when we do prefix sum method we do just 1 arithmetic eqn but for the prefix sum matrix itself we need to run 2 sets of 2 for loops i.e to sum row-wise and then
column-wise therefore their time complexity is also O(mn ).
Then what is the diff between these 2 methods?
is it when the number of queries is more because for 1st method it is QMN and 2nd is M*N+Q
Doubt regarding the time complexity
@namanmittal0007,
You answered it yourself, we reduced O(m*n*q) to O(m*n+q), which means cubic to quadratic, a huge reduction in complexity.
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.