How do you divide the floor of a function?

In the process of finding C and k for Big-O notation (another subject entirely, stupid things), we end up having to do this thing:


And on a related problem:


So… how do you do that? :confused: My first inclination was to pretend the floor and ceiling parts weren’t there, but my first inclinations about math tend to always be horribly, horribly wrong.

Man, that is ugly. Do you actually need to simplify that function, or do you just need a limit? Because the things coverge to limits (that are easy to find by ignoring the floor/ceiling parts).

Um, of course they don’t converge – I mean that each function becomes less and less step-like as it approaches its limit.

Meh. Your k just needs to be large enough, and your C just needs to be small enough. What you should do is bound flo(x) by x-1<= flo(x) <= x, and similarly bound ceil(x). That should be good enough to do your analysis. The easy thing to do is just make k way too big and C way too small. Who cares?

Can you tell I’m already in spring break mode?

floor() and ceiling() don’t affect the asymptotic growth of a function. If f(n) is O(g(n)), then floor(f(n)) is O(g(n)), and ceiling(f(n)) is O(g(n)).

Unfortunately, we have to find the closest possible C and k. Sucks, I know.

The first part of your answer looks good, though. I’ll try that out.


n-1 < floor(n) <= ceiling(n) < n+1

That makes the C really easy to figure out. The k follows quickly from that.