How do you divide the floor of a function?

Factual Questions
1

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:

floor(5x)/x

And on a related problem:

ceiling(x/4)/x

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.

2

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).

3

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

4

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?

5

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)).

6

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.

7

Note:

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

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