The time complexity can not be less than O(n), because any number of the array can not be skipped.
"O(n) or less" should be just "O(n)"

@Alpher Exactly. But ... if the size of the input is less than 3, can we say it is virtually O(1)?