GO Classes Test Series 2023 | Algorithms | Test 1 | Question: 13

Answer 1

Base, $n=1: T(1)=2=A+B+C$

For $n \geq 2$, suppose
$$
\begin{aligned}
&T\left(\frac{n}{2}\right)=A\left(\frac{n}{2}\right)^{2}+B\left(\frac{n}{2}\right)+C \\
&T(n)=4\left[A \frac{n^{2}}{4}+B \frac{n}{2}+C\right]+n+6 \\
&=A n^{2}+(2 B+1) n+(4 C+6) \\
&=A n^{2}+B n+C
\end{aligned}
$$
Then,
$$
\begin{aligned}
&2 B+1=B \Rightarrow B=-1 \\
&4 C+b=C \Rightarrow C=-2
\end{aligned}
$$
From base case, $A+B+C=2 \Rightarrow A=5$
$$
T(n)=5 n^{2}-n-2
$$

Comments

The solution is very good: but there is a little typo

 

4C + b = C 

 

It should be :

 

4C + 6 = C

---

Using base case we can find the answer as B that is fine, but if we’re interested to know the actual value of T(n) then after using substitution method I’m getting it as T(n) = 12n^2 -2n -8 ; hence A+B+C = 12-2-8 = 2.
Please correct me if I’m wrong.

---

Woah, Learned a new way to solve these type of questions.

Answer 2

Answer: B

This is (slightly overcomplicated) another approach to the question using the concepts linear algebra. Basically solving regular quadratic equations in a sophisticated manner.

$T(n)=A n^{2}+B n+C$

 

$T(n)= \begin{cases}4 T(n / 2)+n+6, & n \geq 2 \\2, & n=1\end{cases}$

SInce here we need to find the three unknowns $A, B, C$ we’ll use three equations:

$T(1) = 2 = A + B + C$

$T(2) = 16 = A.2^{2} + 2.B + C$

$T(4) = 74 = A.4^{2} + 4.B + C$

Putting it all in an augmented matrix we get:-

$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 4 & 2 & 1 & 16 \\ 16 & 4 & 1 & 74 \end{array}\right] R_{2} → R_{2} – 4R_{1}; R_{3} → R_{3} – 16R_{1}$

$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & -2 & -3 & 8 \\ 0 & -12 & -15 & 42 \end{array}\right] R_{3} → R{3} -6R_{2}$

$\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & -2 & -3 & 8 \\ 0 & 0 & 3 & -6 \end{array}\right]$

From this: 

$3.C = -6 → C = -2$

$-2.B -3.-2 = 8 → B = -1$

$A + (-1) + (-2) = 2 → A = 5 $

So, $A + B + C = 5 -1 -2 = 2$