big-O and big-omega question

[KataKoniK]

Hi,

I am a bit confused here. Just say you're given code and it says to show the best-case analysis and the worst-case analysis. When you show the best-case, what should the answer be in? In big-O or big-omega? Similarly, if you show the worst-case, what should the answer be in? big-O or big-omega? Would it be correct to just show big-O for worst and best case? I am confused here about when to use both and how to use both when analysing best and worst case.

[0rthodontist]

In each case, choose the option that tells you something about the runtime of the elements of some arbitrary sequence of inputs. Let these runtimes be given by the function A(n).

Now let B(n) denote the runtimes of the elements of a similar sequence of worst-case inputs. You know that A(n) <= B(n). Now do you know anything additional about the long-term behavior of A(n) if you know
a. B(n) \in O(f(n))?
b. B(n) \in \Omega(f(n))?

Choose the one that gives you more information about A(n). And take a similar argument for describing the best case inputs.