Hello, everybody! Recently i was solving a problem [League](https://atcoder.jp/contests/abc139/tasks/abc139_e) on atcoder.↵
↵
I submitted a solution which according to me is O(N*N*N) and so under the given constraints (N<=1000) should not pass, but since it got accepted ,it suggests the time complexity to be O(n*nN*N). Can someone help me finding its right time complexity.↵
↵
[My Code ]↵
(https://atcoder.jp/contests/abc139/submissions/16770543)↵
↵
My Idea:-↵
We initially maintain an array of pointers ptr[] of n teams each pointing to the very first index in its↵
row i.e setting ptr[i]=1 (in 1 based indexing) for all i from 1 to n. Then untill and unless we could not find any valid match we continue our search (searching two positions i and j such that↵
a[i][ptr[i]]==j and a[j][ptr[j]]==i and mark all such two positions and increment ptr[i] and ptr[j] i.e ↵
ptr[i]++ and ptr[j]++ for every such pair of indices) and so in each iteration of the main while loop we increase day by one (initially day=0.)↵
↵
At last we check if any of the pointer ptr[i]<n which indicates we are short of some matches then our ans is 0 else ans=day.↵
↵
Why it's time complexity should be O(n*n*n)-:↵
The total number of the outermost iteration can be n*n in the worst and in such iteration we are doing linear search through the array of pointers , so it total time complexity should be O(n*n*n). But surprisingly, it seems to be O(n*n). Can someone explain me why is it so? ↵
↵
↵
I submitted a solution which according to me is O(N*N*N) and so under the given constraints (N<=1000) should not pass, but since it got accepted ,it suggests the time complexity to be O(
↵
[My Code ]↵
(https://atcoder.jp/contests/abc139/submissions/16770543)↵
↵
My Idea:-↵
We initially maintain an array of pointers ptr[] of n teams each pointing to the very first index in its↵
row i.e setting ptr[i]=1 (in 1 based indexing) for all i from 1 to n. Then untill and unless we could not find any valid match we continue our search (searching two positions i and j such that↵
a[i][ptr[i]]==j and a[j][ptr[j]]==i and mark all such two positions and increment ptr[i] and ptr[j] i.e ↵
ptr[i]++ and ptr[j]++ for every such pair of indices) and so in each iteration of the main while loop we increase day by one (initially day=0.)↵
↵
At last we check if any of the pointer ptr[i]<n which indicates we are short of some matches then our ans is 0 else ans=day.↵
↵
Why it's time complexity should be O(n*n*n)-:↵
The total number of the outermost iteration can be n*n in the worst and in such iteration we are doing linear search through the array of pointers , so it total time complexity should be O(n*n*n). But surprisingly, it seems to be O(n*n). Can someone explain me why is it so? ↵
↵
