We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This solution is actually asymptotically optimal for time as well as space, a certain amount of condition checking calculations would be required for ANY solution to this problem, and the overhead of storing data to an array is much higher than doing a simple condition check on data that is already loaded into computation registers while iterating through the loop (so your argument makes no sense). To use an array, which is what it seems like you are suggesting as a better solution, would just add several layers of inefficiency and could result in additional computation time as N becomes large due to the overhead involved in needlessly storing and reloading inputs that are not needed for calculation and are not needed beyond a single calculation. Using an array also becomes increasingly inefficient as N grows, because the more space you block out (the larger the array), the harder it is to find contiguous space in memory to store that array (so a lot of behind-the-scenes time consuming data shuffling takes place).
Diagonal Difference
You are viewing a single comment's thread. Return to all comments →
This solution is actually asymptotically optimal for time as well as space, a certain amount of condition checking calculations would be required for ANY solution to this problem, and the overhead of storing data to an array is much higher than doing a simple condition check on data that is already loaded into computation registers while iterating through the loop (so your argument makes no sense). To use an array, which is what it seems like you are suggesting as a better solution, would just add several layers of inefficiency and could result in additional computation time as N becomes large due to the overhead involved in needlessly storing and reloading inputs that are not needed for calculation and are not needed beyond a single calculation. Using an array also becomes increasingly inefficient as N grows, because the more space you block out (the larger the array), the harder it is to find contiguous space in memory to store that array (so a lot of behind-the-scenes time consuming data shuffling takes place).