Search code examples
algorithmlimitcomplexity-theory

Is there an asymptotic limit for x*log(x) in relation to x^a, where a is (1,2)?

I know that O(x) < O(x*logx) and O(x^2)>O(x*logx), but what can we say about O(x^a) ? O(x*logx), where a is between 1 and 2.

Solution

  • The easiest way to analyse this is to declare y=log(x) and rewrite our expressions:

    1. x^a = (2^y)^a 
2. x*log(x) = (2^y)*y

    Now take the logarithm of both:

    1. log ((2^y)^a) = y * a
2. log ((2^y)*y) = y + log(y)

    Subtract y and you get this:

    1. y * (a-1)
2. log(y)

    From this you can see that for all a > 1 expression 1 grows linearly and expression 2 logarithmically, meaning that O(x^a) > O(x*logx) for all a > 1.