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

  • 1
    $\begingroup$ 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? $\endgroup$ Aug 20, 2013 at 3:11
  • $\begingroup$ I would assume that the question asks for worst-case runtimes. The actual runtimes of course depend on the particular instances. $\endgroup$
    – adrianN
    Aug 20, 2013 at 9:18

2 Answers 2


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.