Confusion regarding time complexity

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 :slight_smile:

1 Like

Cleared my doubt thanks! i was mistaking 2s for 10^16 instead of 2x 10^8 silly me :stuck_out_tongue:

you can continue your closing reign by closing this one also @vijju123 XD

Closing reign, lmao XD.

(10^5)^2 is 10^10