Given this sorting algorithm:

Sort(A, n):
    if (n == 1)
    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)
         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?

  • $\begingroup$ There is no asymptotic analysis unless at least one aspect of input is not limited. $\endgroup$
    – greybeard
    May 16, 2020 at 10:09
  • $\begingroup$ @greybeard Can you please elaborate? $\endgroup$
    – Lee
    May 16, 2020 at 10:26
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    May 17, 2020 at 4:47

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

  • $\begingroup$ Am I supposed to count number of comparisons? $\endgroup$
    – Lee
    May 16, 2020 at 10:51
  • $\begingroup$ 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. $\endgroup$ May 16, 2020 at 11:02
  • $\begingroup$ Got it, so I need to ask for a clarification. Thank you $\endgroup$
    – Lee
    May 16, 2020 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.