1
$\begingroup$

Suppose we have 3 algorithms complexity times at the worst case:

  • A = $O(nlogn)$
  • B = $O(n\sqrt{n})$
  • C = $\Theta(n)$

In my opinion, it is not possible to define the best solution, since we don't know how Cgrows. I'd like to confirm if that's correct.

$\endgroup$
  • 2
    $\begingroup$ How do you define the best? The asymptotic best is clear one. Maybe you have some constraints or size input in mind, where hidden C does matter? $\endgroup$ – Evil Apr 27 at 21:25
1
$\begingroup$

Well, we know how the algorithm C running time grows - it's linear, and it's two-side (lower and upper) bound.

However there is still not enough information to choose the best (meaning: fastest in practice) algorithm here, because:

  • We know only upper bounds for algorithms A and B - they might be more efficient than C actually, we just don't know that yet.
  • We don't know constants, hidden in the $\Theta$ bounds - they might make the algorithm C less practical than A or B for limited problem size.

Using the given information we can say only that for some sufficiently large problem size the algorithm C might win over algorithms A and B.

$\endgroup$

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.