# Big O

1. Oct 1, 2007

### Logik

1. The problem statement, all variables and given/known data

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

2. Relevant equations
n/a

3. The attempt at a solution
I really don't know what to do else I wouldn't be here :? Some hints would be appreciated!

2. Oct 1, 2007

### Hurkyl

Staff Emeritus
Definitions are usually a good place to start.

3. Oct 1, 2007

### Logik

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

4. Oct 1, 2007

### Hurkyl

Staff Emeritus
Well, you were given an f(n) and asked to prove
f(n) is O(n(1+sqrt(n))),​
weren't you? ...

5. Oct 1, 2007

### Logik

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

6. Oct 1, 2007

### Hurkyl

Staff Emeritus
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?

7. Oct 2, 2007

### Logik

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: Oct 2, 2007
8. Oct 2, 2007

### NateTG

Well, assuming that the problem is correct, you have a known f(n) and g(n) in the inequality
f(n)< C g(n)

I think you can handle solving that for C.