0
$\begingroup$

Can somebody help me with this recurrence please?

$T(n)=4T(\sqrt{n}/3)+(\log n)^2$

$\endgroup$
2
  • $\begingroup$ This not exactly the same, but maybe this can help you? $\endgroup$
    – Nathaniel
    May 26 at 11:22
  • 1
    $\begingroup$ @Nathaniel yes. i saw that. but this one is so difficult to solve. just because of that division by 3. $\endgroup$ May 26 at 12:19
3
$\begingroup$

The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments.

Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as $$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log_3{2})^2.(\log_3n)^2$$

However, this modification will only bring a change of constant in your final solution. So we can safely assume that the original equation had the base of the logarithm as 3.

You have that $k = \log_2(\log_3n+2)$, and you can substitute this at the end to find your answer.

$\endgroup$
4
  • 1
    $\begingroup$ thanks. i tried to solve this by your solution but i guess somehow its not possible to get rid of that division by 3 to be able to solve this by master theorem. right?? $\endgroup$ May 26 at 12:47
  • $\begingroup$ @maryamghanbari You need just to expand the recurrence a little bit based on the introduced substitution. $\endgroup$
    – OmG
    May 26 at 13:23
  • 1
    $\begingroup$ @maryamghanbari also if you would like to know how I came up with that substitution, I tried to find a sequence {$a_i$} such that $a_{i+1}=\frac{\sqrt{a_i}}{3}$ which is $a_i = 3^2a_{i+1}^2$. You can guess the rest. $\endgroup$
    – bigbang
    May 26 at 13:40
  • $\begingroup$ @bigbang right. i get it now. thank you all. $\endgroup$ May 26 at 15:05
0
$\begingroup$

Master Theorem is for Dividing and Subtracting Function.
The Master Theorem at it's core don't discuss Square Root Function.

Although, some Manipulations can be done.

But for the sake of simplicity, solving by Substitution Method

Given,

$T(n)=4T\bigg(\frac{\sqrt n}{3}\bigg) + (\log(n))^2$

$T(n)=4T\bigg(\frac{n^{1/2}}{3}\bigg) + (\log(n))^2$

$T(n)=4\bigg(4T\bigg(\frac{n^{1/4}}{3}\bigg) + (\log(n^{1/2}))^2\bigg)+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + 4(\log(n^{1/2}))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + (2\log(n^{1/2}))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + (\log(n))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + 2(\log(n))^2$

$T(n)=4^2\bigg(4T\bigg(\frac{n^{1/2^3}}{3}\bigg) + (\log(n^{1/2^2}))^2\bigg)+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + 4^2(\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + {2^2}^2(\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + ({2^2}\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + (\log(n))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + 3(\log(n))^2$

Therefore, for k iterations

$$T(n)=4^kT\bigg(\frac{n^{1/2^k}}{3}\bigg) + k(\log(n))^2$$

Now, Assuming $T(1)=1$

Therefore, put $$\frac{n^{1/2^k}}{3}=1$$

$$n^{1/2^k} = 3$$

$$\frac{1}{2^k}log_3n = 1$$

$${2^k} = log_3n$$ $$k = log_2(log_3n)$$

Thus,

$$T(n)=4^{log_2(log_3n)}T(1) + {log_2(log_3n)}(\log(n))^2$$

Solving Further,

$T(n)=2^{2log_2(log_3n)} + {log_2(log_3n)}.(\log(n))^2$

$T(n)=2^{log_2(log_3n)^2} + {log_2(log_3n)}.(\log(n))^2$

$T(n)=(log_3n)^2 + {log_2(log_3n)}.(\log(n))^2$

Since, we don't know base of logarithm given in Recurrence Relation, and also since base don't matter on applying Base Change Formula

$T(n)=(\log(n))^2 + {log(logn)}.(\log(n))^2$

Therefore, $T(n)$ is $O\bigg((log(logn)). (log n)^2\bigg)$

$\endgroup$
1
  • $\begingroup$ Readers, if you found any Mathematical Calculation Error, then please post comment on this forum. $\endgroup$ Sep 24 at 18:54
0
$\begingroup$

Define S(n) = T(2^n), write down a recursion formula for S, solve it using the master theorem, and then let T(m) = S(log m).

Or calculate T(n) for n = 3^0, 3^2, 3^6, 3^14, 3^30, 3^62 etc. without the master theorem, guess a formula for T(3^(2^k-2), and prove it.

Let D log 3.

If T(1) = c, then T(9) = 4T(1) + (log 9)^2 = 4c + 4D^2.

T(3^6) = 4T(9) + 36D^2 = 16c + 52D^2.

T(3^14) = 4T(3^6) + 196D^2 = 64c + 404D^2.

T(3^30) = 4T(3^14) + 900D^2 = 256c + 2516D^4

Etc.

$\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.