Question:
$T(n)$solves the problem by breaking it up into 4 sub problems of the same kind, each of size $n/4$. The solution to the original problem is obtained by combining the solutions of the $4$ sub problems in time$ n$. Express $T(n) $as a recurrence relation and derive and expression for $T(n)$ in terms of $n$.Assume $T(1) = 2$.
Recurrence relation:
$\frac{2}4 +\frac{2}4+\frac{2}4+\frac{2}4$ $$T(2)=2$$ $\frac{3}4 +\frac{3}4+\frac{3}4+\frac{3}4$ $$T(3)=3$$ $\frac{4}4 +\frac{4}4+\frac{4}4+\frac{4}4$ $$T(4)=4$$ $$T(n)=T(n-1)+1$$ $$T(n)=n$$ for$n≥ 2$
How accurate is the recursive relation and expression for $T(n)$ with reference to the question at hand?
Reread the first two sentences. The point of divide and conquer algorithms is that you take one large problem and cut it into some smaller problems. $T(n)$ is the time to solve a problem of size $n$. How big are the smaller problems you cut it into? $T(that)$ is the time to solve each of the smaller problems. Then you need to combine the smaller solutions into a solution of size $n$. They tell you how long that takes. Does that help write the recurrence? You could review your text's derivation of the time required for sorting, which cuts the problem into two halves. The approach is similar-the point of this problem is to see if you have understood it.
Added: Since you divide the problem into four quarters, solving the quarters takes $4T(\frac n4)$. Then it takes $n$ to combine them, so we have $$T(n)=4T(\frac n4)+n$$