Why does bottom up gets TLE whereas top-down passes time limit

#1

Here is my bottom-up impl : https://ideone.com/WNvAv7
Here is my top-down impl : https://ideone.com/JMTSIA
Please help me pass my Bottom UP code as well.
Thank you

#2

@ayushjain.iitg,
Bottom up code has complexity O(n.log(n)) and n=1e9, It will give TLE. Because in bottom up you are calculating all values of n from 2 to 1e9 in worst case, but for e.g all the values between 1e9-1 and 1e9/2+1 will never be used by dp[1e9] itself. Bottom up is not always feasible.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.