I have two functions, f(n)=log(base 2)n and g(n)=log(base 10)n. I am trying to decide whether f(n) is O(g(n)), or Ω(g(n)) or Θ(g(n)). I thinks i should take the limit f(n)/g(n) as n goes to infinity, and i think that limit is constant so f(n) must be Θ(g(n)). Am i right? Thanks in advance
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
You can rely on a useful and often-forgotten result, that $(\log_a b)(\log_b c) = \log_a c$, so in your problem we'll have $$ (\log_2 10)g(n) = (\log_2 10)(\log_{10} n) = \log_2 n = f(n) $$ so $f(n)$ is just a constant multiple ($\log_2 10\approx 3.32$) of $g(n)$ and hence $f(n)=\Theta(g(n))$. |
|||
|
|
