Best case for sorting algorithm

Question

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?

• greybeard: There is no asymptotic analysis unless at least one aspect of input is not limited.
• Lee: @greybeard Can you please elaborate?
• greybeard: 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.

Answer 1

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

• Lee: Am I supposed to count number of comparisons?
• Yuval Filmus: 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.
• Lee: Got it, so I need to ask for a clarification. Thank you