/sci/ - Science & Math

I have the recurrence F(x)=2F(x/2)+x/log(x)

How do i prove using induction that: F(x) is big-O of log(log(x))?

I need to show F(x) <= c[x*log(log(x))] but I don't know how to prove
c[x*log(log(x/2))] + x/log(x)
is less than
c[x*log(log(x))]

Any help would be appreciated

>>15998733
thank you anon, i'm having a new problem:

i am trying to take the derivative of y = x^[(logx)^2 - 2]

and i am getting the correct answer for d/dx[ln(x^[(logx)^2 - 2])]

but not for d/dx(x^[(logx)^2 - 2]):

i start with: lny = ln(x^[(logx)^2 - 2])
=[(logx)^2 - 2]*ln(x)
=[(logx)^2]*ln(x) - 2*ln(x)

then i take the derivative of both sides and get
1/y dy/dx = d/dx([(logx)^2]*ln(x)) - d/dx[2*ln(x)]

and finally dy/dx = y*( d/dx([(logx)^2]*ln(x)) - d/dx[2*ln(x)] )

but once i multiply it by y it is no longer correct.

I think it has to do with d/dx([(logx)^2]*ln(x)) because this is a chain and product rule combined, and multiplying by y seems to not work.

but when i do this for a problem like y= x^(2x - x^2), then i get a correct answer for both dy/dx = y* d/dx(ln[x^(2x - x^2)]) and for d/dx(ln[x^(2x - x^2)]).

is there a problem with what i have done?