= Solution
For the first <recurrence relation>, the <master theorem> compares $n^2$ with $n^{\log_2 6}$. Since $2<\log_2 6$, the recursive leaves dominate and the answer is \b[$\Theta(n^{\log_2 6})$]. More explicitly, the work at depth $j$ is $n^2(6/4)^j$, a growing <geometric series> that stops at depth $\log_2 n-O(1)$, where its sum has that order.
For the second <recurrence relation>, each step subtracts two and adds one until reaching a base case. For integral $n>4$ there are $\lceil(n-4)/2\rceil$ steps, so $T(n)=1+\lceil(n-4)/2\rceil$ and the answer is \b[$\Theta(n)$].
The third set of printed requirements is inconsistent. The specified base values and its <recurrence relation> give $T(n)=1$ identically, as <strong induction> immediately verifies: $4\cdot1-4\cdot1+1=1$. In particular $T(8)=1$, while the extra condition demands $T(8)>2T(4)=2$. Thus \b[no <function> satisfies all the printed conditions]. Dropping that extra inequality gives \b[$\Theta(1)$].
The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put $U_j=T(2^j)$. Its equation has the general form
$$
U_j=1+(A+Bj)2^j,
$$
because $U_j-1$ has characteristic equation $(r-2)^2=0$. The printed values $U_1=U_2=1$ force $A=B=0$. With suitably different initial values, the condition $U_j>2U_{j-1}$ for arbitrarily large $j$ instead requires $B2^j-1>0$, hence $B>0$ and $U_j=\Theta(j2^j)$, or $T(n)=\Theta(n\log n)$. That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.
Back to article page
