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$
F(n) = 1
Is it correct?