if input size is atmost 10^5 and time limit is 2 sec then what is the maximum time complexity that could get an AC verdict?
nlogn, n*sqrt(n) etc
why i have heard that roughly 10^8 operations can be performed every second so 10^8 will work with 1s time limit so why this will only work with nlgn not with n^2 or n^3
For 10^5 , Upper limit can be O(N x logN x logN).
If in 1 second, 10^8 iterations are performed, then in 2 seconds 2x 10^8 iterations are done. But O(N^2) typically require 10^10 iteration. It is 50 times for, hence you need 50x more time for your code to do the task.
If its still unclear, ask
Cleared my doubt thanks! i was mistaking 2s for 10^16 instead of 2x 10^8 silly me
you can continue your closing reign by closing this one also @vijju123 XD
Closing reign, lmao XD.
(10^5)^2 is 10^10