Best-case running time: upper and lower bound?

Question

In my assignment I was given some information about an algorithm in form of statements. One of these statements was: "the best-case running time of Algorithm B is Ω(n^2);".

I was under the impression that best-case running time of algorithms is always either lower-bound, upper-bound or tight-bound. I am wondering if an algorithm such as this can also have an upper-bound of its best-case running time. If so, what are some examples of algorithms where this occurs?

Yes. You can simply try that for example with binary search. See https://stackoverflow.com/questions/28389065/difference-between-basic-binary-search-for-upper-bound-and-lower-bound — samwise, Nov 14 '17 at 21:33
I have edited to expand on my question as your answers don't answer what I am asking. — Marko Durasinovic, Nov 14 '17 at 21:45
@jdv this question is a poor fit over there - it would be quickly voted down and closed, see [Why do 'some examples' and 'list of things' questions get closed?](https://softwareengineering.meta.stackexchange.com/a/7538/31260). Recommended reading: **[What goes on Software Engineering (previously known as Programmers)? A guide for Stack Overflow](https://softwareengineering.meta.stackexchange.com/q/7182/31260)** — gnat, Nov 15 '17 at 07:35
@gnat, my suggestion was a hint that this question has a subject which is more suited for the other SE site, and that the same research and potential question would be best focused in that manner. Not that the question as it is should be moved there. It was a hint to the OP that this subject is best queried in the context of Software Engineering or whatever, not SO. — , Nov 15 '17 at 16:01

score 0 · Accepted Answer · answered Nov 14 '17 at 21:58

A case is a class of inputs for which you consider your algorithm's performance. The best case is the class of inputs for which your algorithm's runtime has the most desirable asymptotic bounds. Typically this might mean there is no other class which gives a lower Omega bound. The worst case is the class of inputs for which your algorithm's runtime has the least desirable asymptotic bounds. Typically this might mean there is no other class which gives a higher O bound. The average case has nothing to do with desirability of bounds but looks at the expected value of the runtime given some stated distribution of inputs. Etc. You can define whatever cases you want.

Imagine the following algorithm:

Weird(a[1...n])
    if n is even then
        flip a coin
        if heads then bogosort(a[1...n])
        else if tails then bubble_sort(a[1...n])
    else if n is odd then
        flip a coin
        if heads then merge_sort(a[1...n])
        else if tails then counting_sort(a[1...n])

Given a list of n integers each between 1 and 10, inclusive, this algorithm sorts the list.

In the best case, n is odd. A lower bound on the best case is Omega(n) and an upper bound on the best case is O(n log n).
In the worst case, n is even. A lower bound on the worst case is O(n^2) and there is no upper bound on the worst case (since bogosort may never finish, despite that being terribly unlikely).
To define an average case, we would need to define probabilities. Assuming even/odd are equally likely for all n, then there is no upper bound on the average case and a lower bound on the average case is Omega(n^2), same as for the worst case. To get a different bound for the average case, we'd need to define the distribution so that n being even gets increasingly unlikely for larger lists. Maybe the only even-length list you typically pass into this algorithm has length 2, for example.

I read on a tutorial that the average case always uses Theta notation. Why can we use Big Omega and Big O for it too? — David G, Nov 14 '17 at 23:13
@0x499602D2 Why not? Did your tutorial explain that Theta is simply the intersection of Big O and Big Omega? Why those bounds would have to be the same in the average case is a mystery to me. — Patrick87, Nov 15 '17 at 00:03

Best-case running time: upper and lower bound?

1 Answers1