# Prove that f(n) = n * log (n) is O(n(1+sqrt(n))).

## Homework Statement

Prove that f(n) = n * log (n) is O(n(1+sqrt(n))).

n/a

## The Attempt at a Solution

I really don't know what to do else I wouldn't be here :? Some hints would be appreciated!

Hurkyl
Staff Emeritus
Gold Member
Definitions are usually a good place to start.

f(n) is O(g(n)) if and only if there exists an n_0 part of natural numbers and a constant C that is part of rational numbers for which f(n) <= that c*g(n) for all n >= n_o

I know the def just don't know how to get g(n)...

Hurkyl
Staff Emeritus
Gold Member
f(n) is O(g(n)) if and only if there exists an n_0 part of natural numbers and a constant C that is part of rational numbers for which f(n) <= that c*g(n) for all n >= n_o

I know the def just don't know how to get g(n)...
Well, you were given an f(n) and asked to prove
f(n) is O(n(1+sqrt(n))),​
weren't you? ...

yes well I don't know how to go from f(n) to g(n)... the examples I have seen were just that you would multiply so part of f(n) until you could group everything together to get c* g(n) but this time I don't see how I can multiply anything to get anything that looks like g(n)...

Hurkyl
Staff Emeritus
Gold Member
yes well I don't know how to go from f(n) to g(n)... the examples I have seen were just that you would multiply so part of f(n) until you could group everything together to get c* g(n) but this time I don't see how I can multiply anything to get anything that looks like g(n)...
I think I had misunderstood you -- your last post sounded like you said you didn't know what g(n) was.

Did you try solving for c? What did you get?

I don't know where to start to solve for c.. that is my problem...

I don't understand where the 1 comes from... I know O(logn) < O(sqrt(n)) so I can get that but where is the (1+srt(n)) comes from?

Last edited:
NateTG