Примените основную теорему о T(n) = T(n/2) + n

Question

Я просто пробовал свои силы в основной теореме и немного запутался, когда пытался оценить T(n) = T(n/2) + n. Используя основную теорему, ответ оценивается как O(n).

Но просто пройдите приведенный ниже код:

fun(n)
{
    if(n == 1)
        return ;
    for(int i=1;i<=n;i++)
    {
        printf("*");
    }
    fun(n/2);
}

Уравнение рекурсии для приведенного выше кода имеет вид T(n) = T(n/2) + n. Таким образом, временная сложность для вышеуказанной программы должна быть O(n).

Но если вы мыслите логически, то количество раз, которое программа запускает, равно: n+n/2+n/4+n/8+...... = nlogn. Таким образом, логически сложность времени для вышеуказанной программы должна быть O(nlogn).

Я очень смущен сейчас. Может кто-нибудь помочь мне, где я неправильно понимаю?

Answer 1

Нет, серия оценивается в 2n.

n + n / 2 + n / 4 + n / 8 +...... = 2n

Но если бы вы имели T(n) = 2T(n/2) + n, то это было бы O( n log n)