Какова сложность времени наихудшего случая для этого кода?

Question

У меня была викторина в классе, и я не очень хорошо с ней справился. Я пытаюсь выяснить, может ли кто-нибудь объяснить мне, что я здесь сделал неправильно - наш профессор перегружен рабочими часами, когда мы перешли в онлайн, поэтому я решил опубликовать здесь.

def functionA(n):
    level = n 
    total = 0
    while level > 1:
        for i in range(0,n):
            level = level // 2
            total = total + i
    return total

Мой ответ: вышеупомянутая функция O (log n), потому что for l oop делит переменную уровня пополам на каждой итерации.

Я получил 5/10 баллов, но на самом деле нет объяснения того, что было неправильно или правильно. Что я не так понял и почему?

Изображение для доказательства того, что тест уже оценен и возвращен. Просто пытаюсь понять это.

Answer 1

Проблема в этой строке:

for i in range(0,n):

Поскольку n и level - две полностью независимые переменные, которые являются копиями n и n, никогда не меняется, это l oop всегда O (n).

Как только мы установили, что внутренний l oop есть O (n), нам нужно выяснить сложность внешнего l oop.

На первой итерации внешнего l oop внутренний l oop многократно устанавливает level = level // 2. Поскольку это назначение быстро сократит level до 1, внешний l oop гарантированно прекратит работу после первой итерации, что сделает его постоянным временем.

У нас осталась общая сложность O ( о) для одной итерации внутренней for l oop.