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.
Subtracting from what exactly? What can you subtract from if you don't know the rest of the array? O(n) means that you are able to solve this while reading the numbers in. If you read the array first and then work on top of it it's not O(n).
Yeah you would have to read the numbers into the array first, and yeah that could definitely potentially mean going through the entire array twice, or one and a half times, etc. But it should be noted here that this is still considered a linear rate of growth, and thus stated generally to be O(n). The fact that it could potentially be 2n does not matter much in the long run, what's important is that it's linear. That's how big O notation is typically used and it is to give a general idea of the eventual rate of growth.
It's O(2n) because you have to have the sum before you can look for the pivot, and worse case this takes two full traversals of the array, minus the first and last elements, but if the array is very large leaving those two elements out makes little difference to the worst-case time. So in the limit where n goes to infinity and the inputs are stacked against you, it takes 2n steps through the array to find the answer.
And that's only if you combine the summing with the inputting. If you do all the inputting and then do the summing and then do the searching, it's O(3n).
Big O notation ignores the constant factor. Whether your code goes through the array once, twice or even a hundred times, it is still O(n), as long as the number doesn't increase as n increases.
Sherlock and Array
You are viewing a single comment's thread. Return to all comments →
Subtracting from what exactly? What can you subtract from if you don't know the rest of the array? O(n) means that you are able to solve this while reading the numbers in. If you read the array first and then work on top of it it's not O(n).
Yeah you would have to read the numbers into the array first, and yeah that could definitely potentially mean going through the entire array twice, or one and a half times, etc. But it should be noted here that this is still considered a linear rate of growth, and thus stated generally to be O(n). The fact that it could potentially be 2n does not matter much in the long run, what's important is that it's linear. That's how big O notation is typically used and it is to give a general idea of the eventual rate of growth.
I understand and agree... I was just confused by everyone talking about having solved it in a single pass.
From my point of view it is not even O(2n). We should take in count complexity of solving algorithm, not complexity of preparing input data.
It's O(2n) because you have to have the sum before you can look for the pivot, and worse case this takes two full traversals of the array, minus the first and last elements, but if the array is very large leaving those two elements out makes little difference to the worst-case time. So in the limit where n goes to infinity and the inputs are stacked against you, it takes 2n steps through the array to find the answer.
And that's only if you combine the summing with the inputting. If you do all the inputting and then do the summing and then do the searching, it's O(3n).
Big O notation ignores the constant factor. Whether your code goes through the array once, twice or even a hundred times, it is still O(n), as long as the number doesn't increase as n increases.
From my point of view it is not even O(2n). We should take in count complexity of solving algorithm, not complexity of preparing input data.
so can you please tell me how to reduce it ? i mean the complexity? because i am not able to clear 1 test case.
Do you have trouble with test case that is posted for this task? If so I posted above implementation that passed all tests for this task.