Решение рекуррентности T(n) = T(n / 2) + O(1) с помощью основной теоремы?

Question

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

T(n) = T(n/2)+O(1)

является

T(n) = O(log(n)) ?

Любое объяснение будет оценено!!

Answer 1

Ваше повторение

T(n) = T(n / 2) + O(1)

Так как основная теорема работает с повторениями вида

T (n) = aT (n / b) + n^c

В этом случае у вас есть

• а = 1
• б = 2
• с = 0

Так как c = log_b a (так как 0 = log₂ 1), вы в случае два из основной теоремы, которая решает в Θ (n^c log n) = Θ (n⁰ log n) = Θ (log n).

Надеюсь это поможет!