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?

  • $\begingroup$ I don't know what the "unrolling technique" is, but I'm puzzled by the term $A(n/7^k)$ that you say it produces. In these studies it is generally the case that $A$ is a sequence - put another way, a function of an integer argument - but $n/7^k$ is rarely an integer, so $A(n/7^k)$ appears to be nonsensical. What's really happening here? $\endgroup$ – Gerry Myerson Jan 23 '12 at 3:01
  • $\begingroup$ I just want to get a running time complexity (using Big-O notation) of above equation. $\endgroup$ – user482594 Jan 23 '12 at 3:10
  • $\begingroup$ You have 3 equations above, and I do not know which one you are referring to. Also, one usually talks about the running time of an algorithm, not of an equation, so again you have me confused. Perhaps you should take the time to think about what it is that you really mean to ask, and then ask it precisely and unambiguously. Oh, and why the "divergent series" tag? I don't see any series here, divergent or otherwise. $\endgroup$ – Gerry Myerson Jan 23 '12 at 4:59
  • $\begingroup$ It seems that your previous questions (at least this one but perhaps also this one) make a similar assumption about a connection between recurrence relations and complexity analysis. Note that, while recurrence relations often occur in complexity analysis, they are much more general than that, and you can't assume that if you talk about recurrence relations people will assume a complexity analysis context. Even given such a context, as Gerry pointed out, it's not the equation that has complexity. $\endgroup$ – joriki Jan 23 '12 at 6:19
  • $\begingroup$ I am sorry for not stating complexity analysis. I should have noted that in the question. The answer from @marty_cohen helped me a lot. $\endgroup$ – user482594 Jan 23 '12 at 6:39

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

  • $\begingroup$ Thanks a lot! I now understands how it works! $\endgroup$ – user482594 Jan 23 '12 at 6:37

Your Answer

