Нижняя граница времени сложность логарифмических уравнений

Question

Вот уравнение:

Верхняя граница:

Без журнала я понимаю верхнююпределом будет O (n ^ 2), но с журналом будет ли верхняя граница O (log n ^ 2)?Или лог отрицается?

Нижняя граница:

Если мы предположим, что это выполняется только один раз, то не должно ли это быть ограничено снизу O (1)

Answer 1

Прежде всего, нижняя граница помечается как Ω, а не как O.

Кроме того, Ω(1) является нижней границей, но она не является жесткой, поскольку для n >= 3:

2log(3n + n^2) > log(n) = Ω(log(n))

и для верхней границы:

2log(3n + n^2) < 2 * log(n^3) = 6log(n) = O(log(n))

А поскольку F(n) = O(log(n)) и F(n) = Ω(log(n))

это означает, что это жесткая граница ион помечен как: Θ(log(n))

Answer 2

log(n^2) = 2*log(n).Это значит O(log n^2) = O(log n).