Also what would be the greatest upper-bound function of time complexity that would run in under 1 sec ?
I always try to suit my solution in the range of about 10^6-10^7 operations and it never exceeds time limit . And the upper bound function depends upon the problem you are doing . Every problem has its own upper bound.
Somewhere between 1e8 and 1e9
Sometimes when my program runs in 1e9 operations on a problem with time limit 1 sec it gives me TLE.
Its simple.
When your code is taking 1e9 operations, then you cannot apply usual theory. You have to consider constant, and other factors. In best circumstances, a code having cheap operations, can do 1e9 in 1 second. Now just add something costly like pow function in it, and it will take over 5seconds.
Have a strict upper limit and {10}^{8}. If you are in range pf {10}^{7}, hardware optimizations wont matter, but in range of {10}^{8}, even a constant factor K=20 can time out your code. Its really sensitive in this region, so give your best every time you can.
1 Like
That’s because operations are 1e9 but you didn’t consider the ‘extra’ work the cpu might have to do depending on the operations you’ve used. For example you cannot multiply long integers 1e9 times since multiplication is costly. ( You can add/subtract them since addition and subtraction is comparatively cheaper)