Qual a relação entre as funções logarítmicas: f(n)=\log _{2} n e g(n)=\log _{3} n ?

Passo 1

O enunciado pede para relacionar as funções
f(n)=\log_{2}n e g(n)=\log_{3}n.
O conteúdo usado será a mudança de base de logaritmos, que mostra como um logaritmo em uma base pode ser expresso em outra base.

Passo 2

A fórmula de mudança de base diz que, para quaisquer bases a>0, c>0 (com a\neq1, c\neq1):
\log_{a}n \;=\;\frac{\log_{c}n}{\log_{c}a}.
Aplicando com a=2 e c=3, obtemos
\log_{2}n \;=\;\frac{\log_{3}n}{\log_{3}2}.
Logo,
f(n)=\log_{2}n \;=\;\frac{1}{\log_{3}2}\;g(n).

Passo 3

Como \log_{3}2 é apenas uma constante positiva, concluímos que f(n) e g(n) diferem por um fator constante. Em termos de notação de complexidade assintótica:
f(n)\;=\;\Theta\bigl(g(n)\bigr), \quad g(n)\;=\;\Theta\bigl(f(n)\bigr).
Isto também implica
f(n)\in O\bigl(g(n)\bigr) \quad\text{e}\quad f(n)\in \Omega\bigl(g(n)\bigr).

Resposta

\displaystyle f(n)=\frac{1}{\log_{3}2}\,g(n) e, portanto,
f(n)=\Theta\bigl(g(n)\bigr).

Exercícios relacionados