0
$\begingroup$

Given $H(x) = lg(f(n))$, where $f(n)$ is an asymptotically positive function, is it always true that if $f(n) = \Theta(g(n))$, then

$H(x) = lg(\Theta(g(n)))$

$\Rightarrow H(x) = \Theta(lg(g(n)))$

To illustrate, Is $lg(n + c) = \Theta(lg(n))$ provided that $c > 0$ and $c$ is a big number?

  • 2
    It is not always true that if $f(n) = \Theta(g(n))$ then $\log f(n) = \Theta(\log g(n))$. For example, take $f(n) = 2$ and $g(n) = 1 + 1/n$. Then $f(n) = \Theta(g(n))$ but $\log f(n) \neq O(\log g(n)) = O(1/n)$. As for your example, $\log(n+c) = \log n + O(1/n)$, so that $\log(n+c) \sim \log n$.2012-03-18
  • 0
    Please use `\log` or `\ln`.2012-03-18

1 Answers 1