Relations between different time complexities of an algorithm

Question

If I have an algorithm A that, in the worst case, has a lower bound of $Ω(n\log n)$ and an upper bound of $O(n²)$, how can I go about determining possible time complexities for best and average cases?

For instance, only one of the following is possible:

a. Best case $\Theta(n)$

b. Worst case $\Theta(n\sqrt{n})$

c. Average case $\Theta(n^3)$

d. Worst case $\Theta(n)$

Now right off the bat I know we can eliminate (d) since it’s also dealing with the worst case, and being that $n$ is out of the given bounds, falling below $n\log n$.

What I’m stuck on is how to approach the other worst case option since it falls in the range and am even more confused about how to deal with the two choices that aren’t even worst case.

Answer 1

Let us use the following notations:

• $L$ is any lower bound on the running time.
• $U$ is any upper bound on the running time.
• $B$ is the best case running time.
• $W$ is the worst case running time.
• $A$ is the average case running time.

These parameters are related in the following way:

$$ L \leq B \leq A \leq W \leq U. $$

You can solve the question using these relations.

Make sure that you understand why they hold.