Upperbounds of functions

1. Jan 23, 2013

sneaky666

Lets say if g(n) is not an upper bound on f(n), then does that mean g(n) is a lower bound on f(n)?
Can anyone help with this please?

Last edited: Jan 23, 2013
2. Jan 23, 2013

Simon Bridge

depends: how did you find g(n)? does f(n) have to be bounded at all?

3. Jan 23, 2013

sneaky666

They are functions that map N to N (natural numbers).
I guess f(n) is just an arbitrary function.

4. Jan 24, 2013

Simon Bridge

... good, what I figured, and the answers to the questions?

Since f(n) is an arbitrary mapping N to N, does it have to be bounded? Can it not be unbounded in both directions? What does this say about g(n) as a bound?

You did not say that g(n) is arbitrary - so how is it found? Is it selected from all possible N to N mappings to have some special relationship with f(n)?

5. Jan 24, 2013

sneaky666

f(n) and g(n) is arbitrary. Both map from N to N.

I think that the statement in the first post is true but I just don't understand how to show this...

6. Jan 24, 2013

Simon Bridge

Line 2, post #4 remains unanswered. It is a repeat of a question asked in post #2.
(If you did answer it, I missed it.)