Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  Gerry Myerson Jan 23 '12 at 3:01
    
I just want to get a running time complexity (using Big-O notation) of above equation. –  user482594 Jan 23 '12 at 3:10
    
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. Also, in the event that this is a homework problem, you should include the "homework" tag. –  Gerry Myerson Jan 23 '12 at 4:59
    
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. –  joriki Jan 23 '12 at 6:19
    
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. –  user482594 Jan 23 '12 at 6:39
show 1 more comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Thanks a lot! I now understands how it works! –  user482594 Jan 23 '12 at 6:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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