You should be able to achieve
O
(
n
) time.