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.