Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.
We denote the worst time complexity of each one by $g_A(n),g_B(n)$
Also, we know there's a positive function $f(n)$ such that $g_A(n)\in\Omega(f(n))$
Is it possible that $g_B(n)\in\Omega(f(n))$? Is it necessary?
It seems naive to think that it's necessary, but I can't figure out to contradict it.
It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$.
It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$.
To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$.
From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$. This implies that, for the same value of $n_0$ and $c$, $2 g_A(n) \ge 2 c f(n) \ge c f(n)$, i.e., $ 2 g_A(n) \in\Omega(f(n))$.
