While flipping through the recursion section of some algorithms text, I got curious as to whether Indeed, it is true. Below is a proof I came up with that interestingly enough exploits the fact that any ceiling function can be written as an optimization problem. Proof. Using simple algebra, we may rewrite the nested ceiling …

Continue reading "Proving ceil(ceil(x)/a) = ceil(x/a) using Optimization"

Advertisements