relations between Lower bound of 2 algorithems

Question

I am given two algorithms A and B, with worst time complexity $$ f_A (n) $$ and $$f_B (n)$$ Respectively.Now it is given that:

1. For each n there exists and input x of size n such that the number of steps of A on x is half the number of steps of B on x.

2. $$ f_A (n)=Ω(h(n)) $$ The questions are:

   1. Is it possible that $$f_B (n)=Ω(h(n)) ?$$
   2. Is it necessary that $$f_B (n)=Ω(h(n)) ?$$ Thank you

Answer 1

As $f_A(n)$ and $f_B(n)$ denote the worst case time complexity, the first statement does not allow any conclusions on $f_A(n)$ and $f_B(n)$. It might be the case that $x$ is the easiest input for algorithm $A$ (i.e., $A$ is fast on $x$) and the hardest input for algorithm $B$ (i.e., $B$ is slow on $x$) or vice versa.

This said, it is possible that $f_B(n) = \Omega(h(n))$: Let $A$ be the same algorithm as $B$ but pick one input $x_n$ for each $n$. If the input for $A$ is $x_n$, run the first half steps of $B$ and return 0. Thus, the first condition is met and it holds that $f_A(n) = f_B(n)$ (assuming that there is more than one input of each size).

The answer to the second question is no. Take algorithm $A$ as before, but on an input $x \neq x_n$ for all $n$ run algorithm $B$ exactly $x$ times. Then $f_A(n) = n \cdot f_B(n)$ and, thus, $$f_B(n) = \mathcal{O}\left(\frac{h(n)}{n}\right) \neq \Omega\left(h(n)\right).$$