# How to get the upper, lower and average bound of a given algorithm?

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?

• I suppose that there isn't only one approach. Proving bounds is usually not an easy task. – nbro Jul 8 '18 at 15:34
• 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. – nbro Jul 8 '18 at 15:34
• It okay.Sorry my English writing skill is not much good.I have made some changes to the questions – Kalana Mihiranga Jul 8 '18 at 15:40
• Please, add a space after every period (".") and comma (", "). Furthermore, start every sentence with a capital letter. – nbro Jul 8 '18 at 15:42
• Apply the changes.Okay – Kalana Mihiranga Jul 8 '18 at 15:53

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)$.