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.