0
$\begingroup$

I am having trouble starting this proof and wanted some clarification. Here are the details given:

ArrayList<T> sort (ArrayList<T> A) {
   if (A.size() <= THRESHOLD) {
     ArrayList<T> B = copy(A)
     insertionSort(B)
     returnB
   } else {
    ArrayList<T> B1 = new ArrayList<T>()
    ArrayList<T> B2 = new ArrayList<T>()
    split(A, B1, B2)
    ArrayList<T> C1 = sort(B1)
    ArrayList<T> C2 = sort(B2)
    return merge(C1, C2)
  }
}

Let $T_{THRESHOLD}(n)$ be the maximum number of steps executed by the algorithm when executed on an input array with a positive length $n$. All of the constants used in the equations are all greater than 0.

\begin{equation} T_{THRESHOLD} (n) \leq \begin{cases} \alpha n^2 + \beta n + \delta & \text{if $n \leq \mathrm{THRESHOLD}$}\\ T_{THRESHOLD}(\lceil n/2 \rceil,k) + T_{THRESHOLD}(\lfloor n/2 \rfloor,k) + \gamma n + \zeta & \text{if $n > \mathrm{THRESHOLD}$}\\ \end{cases} \end{equation}

and for positive integers $n$ and $k$:

\begin{equation} T(n,k) = \begin{cases} \alpha n^2 + \beta n + \delta & \text{if $n \leq k$}\\ T(\lceil n/2 \rceil,k) + T(\lfloor n/2 \rfloor,k) + \gamma n + \zeta & \text{if $n > k$}\\ \end{cases} \end{equation}

Then it is asked to prove that if THRESHOLD is a positive integer then $T_{\mathrm{THRESHOLD}}(n) \leq T(n, \mathrm{THRESHOLD})$ for every positive integer $n$.


I was then wondering if it is required to use Constructive Induction for a question like this since the recurrence equations have been provided. Is it also necessary to solve for variables $\alpha, \beta, \delta$ for solving the basis and induction step of the proof? As well, how would you go about doing the induction with two variables (THRESHOLD and $n$). Anything helps, thank you.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.