# Worst-case time algorithm?...which one is faster?

Imagine that an algorithm A runs in worst-case time $f(n)$ and that algorithm B runs in worst-case time $g(n)$. Answer either yes, no, or can’t tell and could you explain me why?

Is A more faster than B, for all $n>n_0$ if $g(h)=Ω(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=O(f(n)\log n)$?

Is A more faster than B, for all $n>n_0$ if $g(n)=Θ(f(n)\log n)$?

• According to me Worst case is merely the upper bound and does not affect the best case. Hence we cant say anything in all the 3 cases...am i right? Aug 20 '13 at 3:11
• I would assume that the question asks for worst-case runtimes. The actual runtimes of course depend on the particular instances. Aug 20 '13 at 9:18

If $g(n) = \Omega(f(n)\log n)$ then for large $n$, $g(n) \geq Cf(n)\log n$ (for some $C > 0$, and so algorithm $B$ takes more time than algorithm $A$ (in the worst case). In other words, algorithm $A$ is faster.
If $g(n) = O(f(n)\log n)$ then all we know is that for large $n$, $g(n) \leq Cf(n)\log n$; it could be that also $g(n) = \Omega(f(n)\log n)$, in which case algorithm $A$ is faster; or it could be that $g(n)$ is constant while $f(n) = n$ (for example), in which case algorithm $B$ is faster; and there are other possibilities.
If $g(n) = \Theta(f(n)\log n)$ then in particular $g(n) = \Omega(f(n)\log n)$, and so we revert to the first case.
I think that the first statement holds true in all cases; as from the definition of $\Omega$ we can say that $g(n)$ is not dominated by $f(n)\log n$ so we can say that $f(n)$ is faster than $g(n)$ since it must hold true for all $n>n_0$. Hence A is faster than B if $g(n)=\Omega(f(n)\log n)$.