Здравствуйте, rFLY, Вы писали:

N>>Всё равно остаётся O(N), хоть и криво.
FLY>А почему O(N)? Сначала пройтись по массиву, потом создать список и заново пройтись, но уже по списку.

Ну так каждая из этих операций имеет ценой длину списка (равной длине массива).
3*O(N) тоже O(N).
Выделение памяти при схеме работы типичного дотнетовского аллокатора, скорее всего, O(1), а остальное у него размазано на другие операции.