I_lOVE_ROMAN's blog

Time Complexity Calculation
By I_lOVE_ROMAN, history, 14 months ago, In English

For this Problem

1829E - The Lakes

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://codeforces.net/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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

each cell will be visited at most once

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      vector<int> ans(n+1);

for (int i=1;i<=n;i++) {
    for (int neighbor : edges[node]) {
        if (neighbor!=parent) {
            ans[node]+=a[neighbor];
        }
    }
}

      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.

      → Reply