.net - Why is List(T).Clear O(N)? -

according the msdn documentation on list<t>.clear method:

this method o(n) operation, n count.

why o(n)? ask because assume clearing list<t> accomplished allocating new t[] array internally. no other class have reference array, fail see harm in approach.

now, maybe stupid question... allocating t[] array o(n)? reason not have thought so; maybe (is lack of c.s. degree showing right now?). if so, suppose explain since, according same documentation quoted above, capacity of list remains unchanged, means array of equal size need constructed.

(then again, doesn't seem correct explanation, documentation should have said "where n capacity"—not count*).

i suspect method, rather allocating new array, zeroes out elements of current one; , i'm curious know why be.

_{*hans passant pointed out in comment lukeh's answer docs correct. clear zeroes out elements have been set in list<t>; not need "re-zero" elements past those.}

as far i'm aware current implementation calls array.clear on internal t[] array, , array.clear o(n) process. (as hans points out in comments, msdn docs correct n in case list's count, not capacity.)

but, if did allocate new t[] array internally, still o(n) process because allocating array of size n involves initialising n elements zero/null/default state.

of course, there's nothing stop sort of internal trickery array initialised length 0 or 42 or whatever , auto-expanded again on-the-fly required, amortising overall o(n) cost.