CODEWITHSUNDEEP
algorithmlinked-list
Cesare
Cesare

Reputation: 9419

Time complexity of linked list traversal in two passes

I know that traversing a linked list from head to tail takes O(n) time. What if we traverse it twice? Is it still O(n), correct? Because I'm basically O(n + n) = O(2n) ~ O(n).

Upvotes: 0

Views: 191

Answers (1)

OmG
OmG

Reputation: 18838

Yes. Indeed you can say if f(n) is in O(n), f(2n) is in `O(n) too. It comes from the definition of the symbol.

By definition there is a constant c > 0 and N0 such that f(n) < c * n for all n > N0. Hence, f(2n) < c' * n for n >‌ N0 / 2 and constant c'. Therefore, f(2n) is in O(n) too.

Notice that the statement "if f(n) is in O(g(n)), also f(2n) is in O(g(n))" is not correct at all! The contradiction example is when f(n) = g(n) = 2^n.

Upvotes: 2

Related Questions