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.
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 →
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.