# Time complexity analysis of 2 arbitrary algorithms - prove or disprove

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))$$.