when I studied time complexity we learned it in terms of Big-Oh notation
But when we give a contest there it is in seconds or milliseconds !
Can you please provide a scale with which I can make a conclusion that
say if time limit is x seconds I need to do in O(nlogn) ?
in one sec c++ can perform around 10^9 operations
so if constraints are like
n<=10^9
then you can go with the solution have time complexity atmax O(n)
if n<=10^6
you can go with o(nlogn) also
if n<=500
you can go with recursive approach as well
in this way you have to determine
i hope this help
if any further doubts feel free to ask
@asaurabh_26
is it ALWAYS necessary that if its given n<=10^9 then we MUST give an O(n) algorithm…as till now I didn’t know about this …
…and I never thought of finding solution with this in mind while solving problems ?
yes if n<=10^9
and you are using O(n^2) approach then it will give TLE