Удвоение переменной цикла делает цикл логарифмическим по сложности. В таких случаях для оценки сложности помогают основные свойства логарифмов.

При смене основания добавляется константный множитель: \log_a n = C*\log_b n. Поэтому под символом Θ или O основание у логарифма опускают. Точно также как опускают константные множители.
Степень аргумента логарифма можно перекинуть в множитель перед логарифмом: \log n^2 = 2 \log n. Как следствие, под символами Θ и O степень у аргумента логарифма можно отбросить — она эквивалентна умножению на константу.

Очень просто запомнить — степень аргумента и основание логарифма смело выкидывайте из рассмотрения! Давайте попробуем это в деле:

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

Θ(1)

Θ(log n)

Θ(n log n)

Θ(n)

Θ(n²)

Θ(n³)

Θ(3n³)