1
$\begingroup$

Prove that if $g ( n ) ∈ ω ( 1 )$ and $f ( n ) ∈ o ( g ( n ) )$, then $2 f ( n ) ∈ o ( 2 g ( n ) )$.

I was going over this question in my Algorithms class and could'nt understand why first condition has to be met. How would $g ( n ) ∈ ω ( 1 )$ affect our reasoning? Also, what would happen if instead of $g ( n ) ∈ ω ( 1 )$, it was $g ( n ) ∈ o ( 1 )$?

$\endgroup$
  • $\begingroup$ Please use MathJax to type equations. The first condition is completely redundant. For any $f,g$: $f = o(g) \implies 2f = o(2g)$. $\endgroup$ – Dmitry Oct 13 '20 at 16:14
1
$\begingroup$

Considering non negative case we have $$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$ From this definition for $\forall C>0,$ we have: $$ C \cdot O(f)= O(C \cdot f) = O(f)$$ It can be written also as: $$C \cdot g \in O(f) \Leftrightarrow g \in O(C \cdot f) \Leftrightarrow g \in O(f)$$ without any additional condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.