Question

(Subject: Data Structures and Algorithms)

(Q) Let $T(n)=T(n/4)+T(3n/4)+n$ and $T(n)= T(n/5)+T(4n/5)+n$.
The former has a solution $T(n) = c n \lg{n}$ and the latter a $T(n) =d n \lg{n}$,
for some constant $c,d$. Which of the $c,d$ is larger?

No justification needed. Just choose the best suitable answer.

(Options)

(i) $c$ is larger

(ii) $d$ is larger

(iii) $c=d$

Answer 1

The answer is option (ii) d is larger.

For the first equation to be satisfied, put the solution into the equation to get
. This simpliefies to
. This gives
. This gives
.

Similar calculation for the second equation will lead to
. Proceeding as earlier gives

Hence the answer is is larger.