I have a problem about measuring the Time Complexity of the Problem

according to me, it should be O(n^3), n^2 due to dp and O(N) due to transitions , so in total O(N^3)

Constraints:

2≤N≤2000

1≤M≤2000

1≤K≤2000

int dp[2][2001][2001];

int fun( vector g[],int node,int dis,int cnt){

if( dis == k+1 ){ if( cnt%2 || node != t ) return 0; return 1; } if( dp[cnt][node][dis] != -1 )return dp[cnt][node][dis]; int ans = 0; for(auto child: g[node]){ int n_cnt = cnt; if( child == x ) n_cnt^=1; ans = (ans%M+fun(g,child,dis+1,n_cnt)%M)%M; } return dp[cnt][node][dis]=ans;

}

It is Atcoder's King Bombee problem! Link: https://atcoder.jp/contests/abc244/tasks/abc244_e

Its O((n+m)*(n)*2)

I understand that dp[2][2001[2001] causes 2*2001*2001

but also there is loop inside which can run upto O(N)

so isn't it should be O( N * 2 * 2001 * 2001 )

Good question, but no. Each edge only counts for two of the nodes. For this to introduce an additional factor of n, every node would need to have every edge. This isn’t the case because across all nodes, the sum of their degrees is bounded by 2*m, instead of just n^2.

So intuitively the bound is something like “for every edge, you look across it 2*2000 times in each direction at worst”.

Thank you for replying,

Can you Please elaborate, I am still in confusion that it should be

2*2001*2001*2001, cnt*node*dis*loop

Because on average (across all nodes) the loop is m/n, not just m. So you can ignore that part essentially.