Big Theta анализ времени выполнения

Question

Я действительно не понимаю 2 вопроса ниже о T (n).Я понимаю, что означает тета, но я не уверен насчет ответа на вопросы.Может кто-нибудь объяснить?

Я думал, что первый был ложным, потому что T (2n / 3) + 1 = Theta (log n), потому что добавленная константа 1 не имеет значения, и log ближе к непрерывному делению пополамно 2n / 3 не

Я думал, что второй из них был верным, потому что T (n / 2) + n = Theta (n * log n), потому что линейное «n *» в Theta представляет «+ n"в T (n / 2) + n" n / 2 "представляет лог n в тета ...

Answer 1

Первое - Θ (log n).
Интуитивно понятно, когда вы умножаете n на постоянный коэффициент, T (n) увеличивается на постоянную величину.
Пример: T (n) = log (n) / log (3/2)

Второй Θ (n).
Интуитивно, когда вы умножаете nс постоянным коэффициентом T (n) увеличивается на величину, пропорциональную n.
Пример: T (n) = 2n