Сложность времени - цикл, деленный на 2, для вложенного цикла

Question

Я застрял на контрольном вопросе для моих будущих промежуточных курсов, и любая помощь очень ценится.

Пожалуйста, смотрите функцию ниже:

void george(int n) {                
    int m = n;                              //c1 - 1 step
    while (m > 1)                           //c2 - log(n) steps
    {                       
        for (int i = 1; i < m; i++)         //c3 - log(n)*<Stuck here>
          int S = 1;                        //c4 - log(n)*<Stuck here>
        m = m / 2;                          //c5 - (1)log(n) steps
    }
}

Я застрял на внутренней стороне цикла forтак как я увеличивается, а m делится на 2 после каждой итерации.

Если m = 100: 1-я итерация m = 100: цикл будет выполняться 100, я повторяю 100 раз + 1 для последней проверки 2-я итерация m = 50: цикл будет выполняться 50 раз, я повторяю 50 раз + 1 дляпоследняя проверка ..... и т. д.

Будет ли это также рассматриваться как log (n), поскольку m делится на 2?

Answer 1

Внешний цикл выполняется log(n) раз
Внутренний цикл выполняется n + n/2 + n/4 +..+ 1 ~ 2*n раз (сумма геометрической прогрессии)
Общее время составляет O(n + log(n)) = O(n)

---

Примечание - если мы заменим i < m с i < n во внутреннем цикле, мы получим O(n*log(n)) сложность, потому что в этом случае у нас есть n + n + n +.. + n операций для внутренних циклов, где число слагаемых равно log(n)