Hello, everybody! Recently i was solving a problem League 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*n). Can someone help me finding its right time complexity.
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?
