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

  • Thread starter Logik
  • Start date
  • #1
31
0

Homework Statement



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

Homework Equations


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!
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Definitions are usually a good place to start.
 
  • #3
31
0
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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? ...
 
  • #5
31
0
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
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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?
 
  • #7
31
0
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:
  • #8
NateTG
Science Advisor
Homework Helper
2,450
6
I don't know where to start to solve for c.. that is my problem...

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.
 

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

Replies
5
Views
13K
Replies
4
Views
2K
  • Last Post
Replies
7
Views
2K
Replies
5
Views
8K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
2
Views
4K
Top