# Best case for sorting algorithm

Given this sorting algorithm:

Sort(A, n):
if (n == 1)
return
isSorted = true
for i=1 to n-1 do:
if (A[i] > A[i+1]):
isSorted = false
temp = A[i]
A[i] = A[i+1]
A[i+1] = temp
end for
if (isSorted)
return
else
Sort(A, n-1)


I'm required to find the upper bound for the best case. My question is - is the best case considered when the array length is 1? Or when the array is already sorted and then the loop runs only once? Or both cases?

Also, I need to find a recursive formula for the worst case. I got to this formula:

if n $$\neq1$$
$$F(n) = F(n-1) + n - 1$$
else
F(n) = 1

Is it correct?

• There is no asymptotic analysis unless at least one aspect of input is not limited. – greybeard May 16 '20 at 10:09
• @greybeard Can you please elaborate? – Lee May 16 '20 at 10:26
• The bounding of function growth is used in characterising algorithm complexity for some measure of problem size growing boundlessly - including best case analysis. Input size 1 simply isn't relevant. – greybeard May 17 '20 at 4:47

We usually measure the running time of algorithm as a function of the length of the input.

For example, when we say that an algorithm runs in time $$O(n\log n)$$, what we mean is:

• For every input of length $$n$$, the algorithm runs in time $$O(n\log n)$$.

This is an example of worst-case complexity. In your case, you are looking for a function $$T(n)$$ which satisfies the following:

• For every input of length $$n$$, the algorithm runs in time at least $$T(n)$$.
• Furthermore, for each $$n$$ there exists an input of length $$n$$ on which the algorithm runs in time $$T(n)$$.

To answer your particular questions: the answer should be a function of $$n$$; and we are looking for the "best-case scenario" of the algorithm for each input length $$n$$. Whether this best-case scenario is the one you said or not, depends on the algorithm. There might be algorithms for which your best-case scenario is actually a worst-case input (we can construct such algorithms artificially).

• Am I supposed to count number of comparisons? – Lee May 16 '20 at 10:51
• In your post, you say that you're required "to find the upper bound for the best case". You never say what is being upper-bounded – time, number of comparisons, or any other complexity measure. Only you (or the person who set the question) can know the answer. – Yuval Filmus May 16 '20 at 11:02
• Got it, so I need to ask for a clarification. Thank you – Lee May 16 '20 at 11:25