Не каждый одинарный цикл for тем не менее имеет линейную сложность. Посчитайте, что будет в данном примере. Обратите внимание на i*=2

var count = 0;
for (int i = 1; i < n; i *= 2)
    count++;

Θ(1)

Θ(log n)

Θ(n log n)

Θ(sqrt(n))

Θ(n)

Θ(n²)

Θ(2^n)