How to solve a recurrence relation involving a ceiling function?
Solution 1
Hint:
$$f(3)=2f(2)-1=3,\\f(4)=2f(2)-1=3,\\f(5)=2f(3)-1=5,\\f(6)=2f(3)-1=5,\\f(7)=2f(4)-1=5,\\f(8)=2f(4)-1=5,\\f(9)=2f(5)-1=9,\\f(10)=2f(5)-1=9,\\f(11)=2f(6)-1=9,\\f(12)=2f(6)-1=9,\\\cdots$$
and a pattern emerges. To make it even more obvious, consider $g(n):=f(n)-1$, and
$$g(3)=2g(2)=2^1,\\g(4)=2g(2)=2^1,\\g(5)=2g(3)=2^2,\\g(6)=2g(3)=2^2,\\g(7)=2g(4)=2^2,\\g(8)=2g(4)=2^2,\\\cdots$$
Solution 2
Hint $$f(n)=2f(1+\lfloor\frac{n}{2}\rfloor)-1$$
Please do tell me how did you solve the rest of problem, as you are able to solve for floor function recurring relation.
Solution 3
Another hint:
Prove by induction that $f(n)$ is constant between one power of $2$ and the next i.e.
$f(n) = f(n+1) \space \forall \space k \ge 1, 2^k < n < 2^{k+1}$
You know that $f(3)=f(4) = 3$ so your base case is $k=1$.
Now you just have to find the value of $f(n)$ at each power of $2$.
Related videos on Youtube
OOD Waterball
Updated on August 01, 2022Comments
-
OOD Waterball over 1 year
I have no idea against ceiling function...
How to solve
$f(n) = 2f(\lceil{\frac{n}{2}}\rceil) - 1, n > 2, $
$f(2) = 2$?
Thanks!
-
Matti P. almost 5 yearsIdea: split $n$ to even and odd numbers. If $n$ is odd, $f_{n+1}$ should be the same as $f_{n}$.
-
Sil almost 5 yearsWrite first couple values, notice a pattern, try to prove the pattern...
-
-
OOD Waterball almost 5 yearsOops, I meant I can solve $f(n) = {f(\lfloor\frac{n}{2}\rfloor)} + 1$ by seeing it as shifting right $n$ in a form of binary numbers. But the one you gave me is out of my ability I just noticed.
-
Lakshya Sinha almost 5 yearsYeah I tried it's difficult even from my side :-)
-
OOD Waterball almost 5 yearsBy observing, I would write $f(n) = 2^{\lceil\log_2 n\rceil - 1} + 1$. Thanks for the hint! I wonder if there are some procedures dealing with ceiling recurrence rather than observing the pattern?
-
Admin almost 5 years@OODWaterball: you can temporarily ignore the floor/ceiling and solve. This usually yields an asymptotically correct solution. In this case, you can solve for $n=2^k$, then use monotonocity arguments to generalize to arbitrary $n$.