For this Problem
The solution is written in O(n*m)
But How it is possible if there is recursion calls inside the nested solution.
Solution in tutorial is:
https://mirror.codeforces.com/blog/entry/116108 (Problem E)
Please someone help me understand the time complexity?Shouldn't it be O(n*m*n*m).I know we are not checking same grid twice.
Please someone help me.
each cell will be visited at most once
I know that.But I am not understanding if there is recursion calls in that O(n*m) nested loop.Shouldn't it be O(n*m*recursioncalls).
No. Loop counts do not matter. Its all about sum. Think of it this way.
"""Given a tree with n nodes and a value for each node ai, calculate the sum of values of their children for each node.
Take a look at this pseudocode.
This piece of code has n loops and it seems like every node can have upto n neighbors so its O(N^2) right? No. Because the sum of neighbor counts of each node is fixed and is linear. So it is O(N).
The same logic can be applied here.