Its o(N) only .The answer is damn Correct!

[arik_ash]

The answer comes out to be O(2N-1/2) = O(N)

{ N + N(N-1)/N + 1/2 }