>>929
ごめんなさい、間違ってた。
前者も後者も時間計算量はO(n)です。

違うのは空間計算量でした。
前者がO(n)
後者がO(1)です。