Proving or disproving a mathematical argument

83 Views Asked by At

I have to either prove or disprove a mathematical argument: $$ \log(f(n)) = o(\log(g(n))\rightarrow f(n) = o(g(n))$$


$small-o$ is an asymptotic notation that is explained below. (the $o$ that appears in the inequality). So, using the definition of $small-o$, this is what I principally have to prove:

$$\log(f(n)) < c \cdot \log(g(n))\rightarrow f(n) < c\cdot g(n)$$

$f(n), g(n)$ are functions that determine the growth in runtime for an input $n$, due to that $n$ is positive. (Computer science stuff, data algorithms and structures)

$c \in \mathbb{R}$, and $c>0$, and the $\log$ is in base $2$.


There is an asymptotic notation called small-o that goes as follows: if we want to prove $f=o(g)$, (f,g are two input functions as described above) we have to show: $$o = \{ f\mid \exists c\in\mathbb{R}, c>0, \exists n_{0}\in \mathbb{N}, \forall n>n_{0} \mid f<c\cdot g\}$$

in our case, it is given.

I can say there is $c>0, c\in \mathbb{R}$, and there is $n_{0} \in \mathbb{N}$, so for every $n>n_{0}$: $$\log(f(n)) < c \cdot \log(g(n))$$


Yet, I stuggle to either prove, or disprove this argument. I tried to use logarithmic rules in order to simplify it into something else, but it didn't really work as expected. If it is, by any chance, not a correct argument, what stance I should use in order to disprove it? Will a negative example be enough?