0

If you have a recurrence relation like the following, when you are solving it by iteration how do you simplify the terms?

$A(n) = A(\left \lfloor{\frac{n}{2}}\right \rfloor)$

and $A(\left \lfloor{\frac{n}{2}}\right \rfloor) = A(\left \lfloor{\frac{\left \lfloor{\frac{n}{2}}\right \rfloor}{2}}\right \rfloor)$

$A(n) = A(\left \lfloor{\frac{\left \lfloor{\frac{n}{2}}\right \rfloor}{2}}\right \rfloor)$

$A(\left \lfloor{\frac{\left \lfloor{\frac{n}{2}}\right \rfloor}{2}}\right \rfloor)= A(\left \lfloor{\frac{\left \lfloor{\frac{\left \lfloor{\frac{n}{2}}\right \rfloor}{2}}\right \rfloor}{2}}\right \rfloor)= A(\left \lfloor{\frac{n}{2^3}}\right \rfloor) ???$

glockm15
  • 587
  • Assuming $n$ is a nonnegative integer, the solutions to this particular recurrence are a constant functions, as you can prove by strong induction. Are you asking for general ideas to solve similar problems? One useful trick is to think about writing $n$ in binary, since $\lfloor n/2\rfloor$ is just $n$ with the last digit dropped. – stewbasic May 31 '18 at 06:22
  • @stewbasic , yes I am looking for general idea to solver similar problems where I am also given a base case: A(1) =0 and A(n) = A(floor (n/2)) + some constant – glockm15 May 31 '18 at 06:31
  • In the case of $A(n)=A(\lfloor n/2\rfloor)+c$, you also use strong induction to show that $A(n)=c\lfloor \log_2n\rfloor$ – Hagen von Eitzen May 31 '18 at 06:36
  • @HagenvonEitzen om, so we can say that $A(⌊n/2⌋)=A(⌊n/2^2⌋)+2C$ ? – glockm15 May 31 '18 at 06:46

0 Answers0