0
$\begingroup$

I tried to solve below recurrence relation with unrolling technique.

$A({n})=4A(\lfloor{n/7} \rfloor)+n^2$ for $n\ge 2$

$A({n})=1$ for $0\le n\le 1$

What I have come up so far is

$A(n) = 4^kA(n/7^k)+4^k\lfloor n/7^k \rfloor ^2 ....+4\lfloor n/7 \rfloor ^2 + n^2$

But I do not understand how I should advance farther from above equation. How can I simplify above statement, and substitute the base case into the equation?

  • 0
    The traditional way to show that an answer helps you is to click on the up-arrow next to it. To show that an answer really answers the question for you, you can click in the check-mark next to the answer. That's how the site works.2012-01-23

1 Answers 1

1

This seems pretty close to the right answer.

When $k = \lceil \ln(n)/\ln(7) \rceil$, $n \le 7^k$, so $A(\lceil n/7^k \rceil) = 1$.

Putting this in your equation, $A(n) = 4^k +4^k\lfloor n/7^k \rfloor ^2 ....+4\lfloor n/7 \rfloor ^2 + n^2 $.

To get an upper bound, since $\lfloor x \rfloor \le x \le \lceil x \rceil < x+1$, $4^k < 4^{1+\ln(n)/\ln(7)} = 4n^{\ln(4)/\ln(7)} < 4n $ so $A(n) < 4n + n^2(4^k/7^k+....+4/7+1) < 4n + n^2/(1-4/7) < 4n + 7 n^2/3 $.

Therefore $A(n) = O(n^2)$.

In this case, the series multiplying $n^2$ converges.

Try to solve this with the 4 and 7 swapped, so that $A({n})=7A(\lfloor{n/4} \rfloor)+n^2$.

  • 0
    Thanks a lot! I now understands how it works!2012-01-23