1
$\begingroup$

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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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