In the video solution, it is said that since N is too large (34), therefore bitmasking will give TLE as 2^34 is not computable within time limits and so we divided the initial array in size of 2. Please tell me upto whic power of 2, the computation is feasible under time constraints and how we check that feasability??
SUBSUMS problem solution being shared inside pdf
2^31 is around 10^9
You are allowed to do operations of order 10^8.
So I guess you shall now know what complexity is feasable.
Okay, so we convert to order of 10 and check if its order is less than 8 or not, if it is not then we start to divide it into different tiles where each tile has order below 8, right?
Yeah!
Most questions asks you to solve it in 2seconds or 5 seconds that means 2*10^8 operations or around.
So before writing any code, just check the complexity of your algo whether it fits in with the given time or not.
Generally:
n=10^7 = O(n)
n=10^5 = O(nlogn)
1 Like