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


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.