3
$\begingroup$

This is probably a very silly question.

If $h(n)=\frac{n}{2}, \ g(n)=n$, so $ \lim_{n \to \infty} \frac{h(n)}{g(n)} = \lim_{n \to \infty} \frac{n}{2n}=\frac{1}{2} $ so $h(n) \leq C_1 g(n), h(n)=O(n)$

at the same time , if $g(n)=\frac{n}{10}$, this limit becomes 5, so

$h(n) \geq C_2 g(n), h(n)= \Omega(n)$

Is this logic correct enough to say that $ \frac{n}{2}=\Theta(n) $

  • 0
    In general, for any function $f(n)$ and any constant $c$, we have $c f(n) = \Theta(f(n))$.2012-01-26

1 Answers 1

3

Yes but note that it also immediately follows from the definitions.

  • 0
    @user19821 yes indeed, it is obvious how you have to choose the constants that it nicely fits the definition.2012-01-24