2
$\begingroup$

We're given the function $T: \mathbb{N} \rightarrow \mathbb{R}$ which takes a constant value for $n \leq 4$ and for all other $n \in \mathbb{N}$ it is through the following recurrence relation defined: $T(n) = 4T(n/2) + n^2\log(n)$.

I need to provide a function $g$, so that $T \in \Theta(g)$.

After drawing my tree, I got to the general equation which says that for $T(n/2^i)$ we'll be at level $i$ and we'll have habe $4^i$ nodes with the sum of the level being $n^2\log(n/2^i)$. So far am I correct?

The next problem I had was that I wasn't sure of my base case, so I assumed $T(1) = 1$, but now thinking about it, it probably has to do with the very first sentence saying that the function takes a constant for an $n \leq 4$, but I'm not sure how to get the base case from that.

Assuming $T(1) = 1$, I went ahead and calculated my $i$ value for the base case: $1 = n/2^i \Rightarrow i = \log_2n$. So out of that, I started summing back up, so I had:

$$T(n) = n^{\log_24} + \sum_{i=0}^{\log n-1}n^2\log\Big(\frac{n}{2^i}\Big) $$ after some simplifying I got to $$n^2 + n^2\Bigg(\sum_{i=0}^{\log n-1}\log n - \sum_{i=0}^{\log n-1}\log 2^i (= i?)\Bigg) \quad $$

Eventually I used some sigma notation rules (first sigma was just a constant being summed up $\log n$ times, second one was the gauß sum up to $\log n - 1$, and got to:

$$n^2 + n^2\Bigg(\frac{\log n^2}{2}\Bigg)$$

I am pretty sure that I made a mistake somewhere, but in case I didn't, I then assumed that $T \in \Theta\big(n^2 ((\log(n))^2\big)$

Any input would be appreciate on how to go about this or where I made a mistake... I've been stuck with this equation for over $5$ hours and can't seem to get it right. Everytime I go at it, I get a different answer.

Thanks!

$\endgroup$
0
$\begingroup$

Your solution is correct. A problem of size $n$ takes $O(n^2\log n)$ time, plus four subproblems that take $\left(\frac n2\right)^2\log\frac n2$, which sum to $O(n^2\log n)$ time. There are $\log n$ levels in the recursion tree, and hence the overall runtime is $O((n\log n)^2)$. Indeed, if we assume that $T(n) \leqslant C(n\log n)^2$ for some constant $C$, then $$ T(2n) = 4T(n) + (2n)^2\log 2n \leqslant 4C(n\log n)^2 + 8n^2\log n\leqslant C'(n\log n)^2 $$ for a constant $C'$, so we conclude by induction that $T(n)\in O((n\log n)^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.