Question

Let f(x) = 2x^3 + 3x log(x). Prove f(x) is O(x^3) by finding values for C and k that satisfy the definition of big-O.

Def: |f(x)| <= C|g(x)| , for all x >= k

Answer 1

@shubhamsrg

Answer 2

ive got C=3 and k=1, but i think my "proof" gets flawed

Answer 3

Please show your working.

Answer 4

Try C = 5 instead :3

Answer 5

Sir first please please please show your working

Answer 6

2x^3 + 3xlog(x) < 2x^3 + 3x^2 < 2x^3 + 3x^3
for all x >=1

Answer 7

Let Cx^3 be a linear combination similar to that of f(x).

Cx^3 = 2x^3 + Nx^3 ; now find a suitable N such that: Nx^3 > 3x log(x)

Nx^3 > 3x log(x) ; divide by x

Nx^2 > 3log(x) ; use log property, p log(q) = log(q^p)

Nx^2 > log(x^3) ; base 2 each side

*****************************************
2^(Nx^2) > x^3 ; base 2 each side again
*******************************************

4N > 3, for all N > 3/4, let N = 1


Cx^3 = 2x^3 + x^3 = 3x^3, Let C = 3

.....................................

now to solve for x


3x^3 > 2x^3 + 3xlog(x)

x^3 > 3xlog(x)

x^2 > log(x^3)

2^(2x) > x^3

4x > 3x, for all x > 0, let k = 1 or more

Answer 8

trying to steer away from log(x) is O(x)

Answer 9

ok

Answer 10

I've actually never heard of this O stuff until now :D

Answer 11

it pretty vague to me too. Just havent had a class that covers it is all

Answer 12

Logs are base 2 in this i believe since its from a computer science course
\[Nx^2~\gt~log_{2}(x^3)\]
\[2^{Nx^2}~\gt~2^{log(x^3)}\]
\[2^{Nx^2}~\gt~x^3\]
\[\Large 2^{2^{Nx^2}}~\gt~2^{x^3}\]
\[2Nx^2~\gt~3x\]
\[2Nx~\gt~3\]
i think thats the way my proof should go, i just assumed that extra 2 base multipled exponentts into 4Nx

Answer 13

N > 3/(2x)

when x=1, N >= 2 would work fine .... and of course C and k need not be unique solutions, just valid solutions

Answer 14

let C = 2 + 2 = 4

4x^3 > 2x^3 + 3x log(x)

2x^3 > 3x log(x)

2x^2 > 3 log(x)

6x^2 > 3x

2x > 1, when x > 1/2, let k=1

Answer 15

<cringing in horror>
O.O

Answer 16

ugh, im still having an issue trying to base out the logs ...

\[\Large N^{p^q}\ne N^{pq}\]
\[\Large (N^p)^q= N^{pq}\]

Answer 17

Why were you steering clear of
log(x) = O(x)
again?

Answer 18

im not sure if the question presupposes that knowledge

Answer 19

Well, maybe not that, but isn't
log(x) < x for all x > 1 anyway?

Answer 20

putting aside all the O stuff... log(x) is simply less than x?

Answer 21

granted we could prove it

\[x>\frac{L(x)}{L(2)}\]
\[x~L(2)>L(x);~~\forall>1\]

Answer 22

lost an x lol

Answer 23

And if you could prove it, then, the part I posted would follow?
2x^3 + 3x log(x) < 2x^3 + 3x^2 < 2x^3 + 3x^3 for all x > 1 (or maybe 2, just to be safe)

Answer 24

yes, that would follow if it was be proved that log(x) is O(x).

Answer 25

Really? It has to be that? and not just
log(x) < x ?
T.T

Answer 26

it has to satisfy the definintion of big-O

Answer 27

Well, that depletes my ideas :D

Answer 28

but if it was proven before hand and assumed to be common knowledge at this point -- then its fine :) im just not sure how much common knowledge the person is that emailed this to me

Answer 29

Ask him? :D

Answer 30

eventually ....

Answer 31

have fun yall

Answer 32

Cheers :)