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.


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.

  • $\begingroup$ Hmm, that leads me to believe the answer is choice b? Being that that appears to be the only one that falls in the range of the bounds? $\endgroup$ – Hello Sep 4 '18 at 2:12
  • $\begingroup$ That's what I think too. $\endgroup$ – Yuval Filmus Sep 4 '18 at 5:39
  • $\begingroup$ Thanks for the help! And also thanks for those relations I'll keep those in mind. $\endgroup$ – Hello Sep 4 '18 at 13:10
  • $\begingroup$ Don’t forget to upvote and accept the answer. $\endgroup$ – Yuval Filmus Sep 4 '18 at 15:11

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.