1
$\begingroup$

How to get upper, lower, average bound of given algorithm? What should be the first step I should do? I search on the internet and only give me the definition of those 3. For example if take the algorithm of nlog(n)+2 then how do we find the lower and upper bound of this? What would be the first step?

$\endgroup$
  • $\begingroup$ I suppose that there isn't only one approach. Proving bounds is usually not an easy task. $\endgroup$ – nbro Jul 8 '18 at 15:34
  • $\begingroup$ I downvoted because you should have put more effort into writing this question. For example, what the heck is "do?search"? Add spaces, etc., where appropriate. $\endgroup$ – nbro Jul 8 '18 at 15:34
  • 1
    $\begingroup$ It okay.Sorry my English writing skill is not much good.I have made some changes to the questions $\endgroup$ – Kalana Mihiranga Jul 8 '18 at 15:40
  • $\begingroup$ Please, add a space after every period (".") and comma (", "). Furthermore, start every sentence with a capital letter. $\endgroup$ – nbro Jul 8 '18 at 15:42
  • 1
    $\begingroup$ Apply the changes.Okay $\endgroup$ – Kalana Mihiranga Jul 8 '18 at 15:53
0
$\begingroup$

When we talk of best case, worst case, and average case, it is in the context of algorithms whose running time depends on the input and not just on its length. If the algorithm always runs in time $n\log n + 2$, then the best case, worst case, and average case are all the same.

For a non-trivial example, consider quicksort. Quicksort always runs in time $O(n^2)$, and there is a sequence of arrays, one of each length, on which quicksort runs in time $\Theta(n^2)$. Therefore the worst case running time of quicksort is $\Theta(n^2)$. The best case running time varies according to the implementation – it can be $\Theta(n\log n)$ or $\Theta(n)$.

What about average case? Whenever we talk about average case, we need to introduce a distribution, according to which the average is taken. For sorting, the standard distribution is a random permutation of $1,\ldots,n$. The average case running time of quicksort, with respect to this distribution, is $\Theta(n\log n)$.

In other words, even though there are some arrays which are "difficult" or "bad" for quicksort, causing it to have quadratic running time, on "most" arrays it behaves much better, having a linearithmic running time. The running time depends not only on the length of the input array, but also on its order. This causes the discrepancy between worst case and average case for quicksort, and for many other (though not all) sorting algorithms.

$\endgroup$

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.