# 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.

## 1 Answer

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

• Yes, that's what I think (I proved it in the same way), but I'm not sure if I'm missing something – Combinatoric May 16 '20 at 16:19
• No.. ? If you proved it then it must be true :) – Steven May 16 '20 at 16:24
• You're right, I'm a newbie so I doubt myself most of the time. – Combinatoric May 16 '20 at 17:13