- #1

Logik

- 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!

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Logik
- Start date

- #1

Logik

- 31

- 0

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

n/a

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

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

Definitions are usually a good place to start.

- #3

Logik

- 31

- 0

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

- #4

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

Well, you were given an f(n) and asked to prove

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

f(n) is O(n(1+sqrt(n))),

weren't you? ...- #5

Logik

- 31

- 0

- #6

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,967

- 19

I think I had misunderstood you -- your last post sounded like you said you didn't know what

Did you try solving for

- #7

Logik

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

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,452

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

Share:

- Replies
- 9

- Views
- 522

- Replies
- 17

- Views
- 105

- Replies
- 12

- Views
- 651

- Replies
- 30

- Views
- 680

- Replies
- 9

- Views
- 214

- Replies
- 51

- Views
- 2K

- Replies
- 5

- Views
- 284

- Replies
- 4

- Views
- 238

- Replies
- 9

- Views
- 175

- Last Post

- Replies
- 9

- Views
- 804