Are you sure you mean O(n) instead of O(1), which I would expect for an array?