2
$\begingroup$

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are two separate concepts, so now I came up with this assertion which I think is correct, but I want to sanity check it:

An algorithm can be said to be optimal if the function that describes its time complexity in the worst case is a lower bound of the function that describes the time complexity in the worst case of a problem that the algorithm in question solves.

As of now what I understand is that the so called bounds are "interactions" between functions and that the "cases" are just particular functions arising from particular situations regarding an algorithm's performance or the number of operations needed to solve a problem. Would that definition of an optimal algorithm be correct?

EDIT: the question is more aimed towards the proper theoretical understanding of cases and bounds than the real life properties of an optimal algorithm that extend to other concepts.

$\endgroup$
  • $\begingroup$ It’s up to you what notion of optimality to use. $\endgroup$ – Yuval Filmus Mar 3 at 7:26
1
$\begingroup$

There are various notions of optimality one can think of. One popular notion of optimality is worst-case running time, which is what you describe:

An algorithm for solving a problem $P$ is asymptotically optimal with respect to worst-case running time if it runs in time $T(n)$, and any algorithm for $P$ runs in time $\Omega(T(n))$.

In fact, this notion is ambiguous, since it's not clear what the parameter $n$ is. Indeed, in some cases there are several relevant parameters, which we sometimes want to consider at the same time. This is the case with graph algorithms, in which there are two natural parameters: the number of vertices and the number of edges.

An additional point of ambiguity is the computation model against which everything is measured. In theoretical work, we usually consider the word RAM as our computation model, but other models are possible.

The definition above is about the asymptotic running time. This manifests itself in two ways. First, we only care about the time complexity of the algorithm up to constant factors. Second, we only care about the behavior for large $n$. In practice, sometimes $n$ is fixed, and then the definition above doesn't make any sense.

Whereas worst-case running time is a popular parameter, other parameters are also relevant. Some examples include average-case running time (whenever there is a natural input distribution) and memory consumption. Only you can say which notion of optimality is most relevant for you.

$\endgroup$
  • 1
    $\begingroup$ Of course, many algorithms with the same optimal $\Theta$-runtime "complexity" can exist. Among those, we need higher-resolution notions to decide which we want, and usually there are trade-offs rather than clear winners. $\endgroup$ – Raphael Mar 3 at 8:59
  • $\begingroup$ the question was more aimed towards a definition related to worst-cases, I'm sorry if it went misunderstood. I'm also not very keen about the title change of the question because of this. $\endgroup$ – MikeKatz45 Mar 3 at 9:01
  • 1
    $\begingroup$ Perhaps this question is relevant? cs.stackexchange.com/questions/23068/… $\endgroup$ – Yuval Filmus Mar 3 at 9:05
  • $\begingroup$ It does help a bit, thanks. When you mentioned the notion of optimality regarding worst case running time, it seems like your definition states the algorithm is optimal if no better algorithm exists, however I understand that optimality in these terms arises from comparing the algorithm to the problem and not to other algorithms. $\endgroup$ – MikeKatz45 Mar 4 at 1:24
  • $\begingroup$ We define the complexity of a problem via algorithms solving it. $\endgroup$ – Yuval Filmus Mar 4 at 6:45

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.