Failing perf tests


Time complexity for my approach is O(n) whereas the prescribed method has O(nlogn) complexity. Is there a mistake in my calculation? if not, then why am I failing perf tests.
Note: All base and edge cases are passing.

The alternative approach also suggest a O(M+N) complexity. Were you able to get the testcases to download (top right bulb icon) and see where things are slowing down?

The perf 10 test case is very big and difficult to be debugged manually.
perf_test-10
Can you suggest a smaller test set to debug the issue?

@m_a_x_i_m_u_s Hey can you explain why is your complexity O(N)?

Note : Dimensions of matrix are M * N.

@m_a_x_i_m_u_s

The complexity of your solution is O(N * M) and not O(N).

The recurrence equation of the code you have written is T(N * M) = T(N/2 * M) + T(N * M/2)

let us assume N is almost equal to M i.e it’s an almost square matrix
so if we rewrite the equation by replacing M with N.

T(N^2) = T(N^2/2) + T(N^2/2)

Let N^2 be A
so T(A) = T(A/2) + T(A/2) + 1==> 2T(A/2) + 1

we know the solution to this recurrence to be O(A) (Link : https://medium.com/@randerson112358/iteration-substitution-method-1dc0cf6fe87a)

Replace A again i.e O(N ^ 2) so it’s O(N*M)

So explains why your solution is failing performance cases. Optimize the solution to pass all the cases

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.