если в Лине лазить только по банкам, из нее вряд ли что-то атакует Винду"вряд ли" != 100%.
подходящестиудачный термин для нечёткой выборки))
Там работы с деком и если присмотреться то станет понятно, что каждый элемент последовательности в худшем случае будет помещён в дек не более одного раза и не более одного раза покинет дэк.нет. Тут ошибка!
Соотвественно это все равно O(n)
он не линеен, насколько я понимаю.точнее, сложность O(n log n).
Как вы правильно заметили у него сложность (log n)