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$ – winston smith Aug 20 '13 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 '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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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