f(n)/log(n) = O(g(n)) ⇒ g(n) = Θ(f(n))?

Question

Можно ли показать, что f(n)/log(n) = O(g(n)) => g(n) = Θ(f(n))?

Прямо сейчас я стою здесь:

1. f(n)/log(n) = O(g(n)) ⇒ f(n)/log(n) ≤ c₁⋅g(n) ⇒ f(n)/(c₁⋅log(n)) ≤ g(n)

2. g(n) = Θ(f(n)) ⇒ c₂⋅f(n) ≤ g(n) ≤ c₃⋅f(n)

Тогда я говорю: c₂ = 1/(c₁⋅log(n)) ⇒ c₂⋅f(n) ≤ g(n)

Если это правильно, как мне показать верхнюю границу?

Answer 1

Нет, это не близко к правде. Есть две проблемы. Во-первых, отношение Theta включает как верхнюю, так и нижнюю границы, но (как вы заметили) вы только предполагаете, что g дает верхнюю границу для f. Так, например, попробуйте f(n) = 0 и g(n) = n: предположение верно, но вывод неверен. Во-вторых, коэффициент log(n) не является постоянным фактором, который также помешает вам установить тесную связь между f и g; например, см. комментарий от @templatetypedef.

Answer 2

Как было сказано ранее, вы можете опровергнуть предположение с помощью (общего) примера:

Позволять f(n) = g(n) ⋅ log(n), затем f(n)/log(n) ∈ O(g(n)) держит, но очевидно g(n) ∉ Θ(f(n)),

То, что вы можете показать, это:

f(n)/h(n) ∈ Θ(g(n))   ⇒   g(n) ∈ Θ(f(n)/h(n))   ⇒   g(n) ∈ O(f(n))