Sherlock and Array

  • + 1 comment

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