Solving recurrence relation containing floor $A(n) = A(\left \lfloor{\frac{n}{2}}\right \rfloor)$

454 Views Asked by At

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) ???$