1
$\begingroup$

Problem

Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates.

sort(A, i, j)
  if i = j
    return
  m = floor[(i + j)/2]
  sort(A, i, m)
  sort(A, m + 1, j)
  if A[m] > A[j]
    swap A[m] and A[j]
  sort(A, i, j - 1)

Write a recurrence that characterizes the runtime of sort(A, 0, n-1).

Attempted Solution

Let $T(n)$ be the run-time of sort(A, 0, n-1)

if i = j then return $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

m = floor[(i + j)/2] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, m) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

sort(A, m + 1, j) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

if A[m] > A[j] then swap A[m] and A[j] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, j - 1) $\hspace{0.1cm} = \hspace{0.1cm} T(n - 1)$

$\therefore T(n) \hspace{0.1cm} = \hspace{0.1cm} 2 \hspace{0.1cm} T(\frac{n}{2}) \hspace{0.1cm} + \hspace{0.1cm} T(n - 1) + \hspace{0.1cm} O\hspace{0.01cm}(1)$

Is this correct? Feedback would be greatly appreciated.

Sort in Action

The sort algorithm actually works. See this example to convince yourself.

https://imgur.com/G5FUewE

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ does this really sorts? $\endgroup$ – kelalaka Oct 9 '18 at 8:57
  • $\begingroup$ Yes it does. But that is besides the point here, I need a recurrence. $\endgroup$ – turing Oct 9 '18 at 9:02
  • $\begingroup$ Yes, your argument is correct. $\endgroup$ – kelalaka Oct 9 '18 at 9:05
  • $\begingroup$ Wonderful, thank you. I posted a pic where I compiled this algorithm with a test case - it actually sorted! $\endgroup$ – turing Oct 9 '18 at 9:06
  • $\begingroup$ Yes, I looked again and saw that, apart from exercise, no use. $\endgroup$ – kelalaka Oct 9 '18 at 9:07
1
$\begingroup$

This is just Bubble-Sort in disguise. Each time, you get the biggest element pushed to the end of the array, then you sort the remaining of the array.

Your recurrence is correct.

An upper bound would be $T(n) = O(2^n)$.

Proof: For large enough $n$, we have $T(n)\leq 2^n$. This is the base case for induction. Induction hypothesis is $T(n)\leq 2^n$. So, we have $$2\sqrt{2^n}+\frac{2^n}2+O(1)\leq 2^n$$.

| cite | improve this answer | |
$\endgroup$

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.