Find the big-O of a function

Question

Please help me on following two functions, I need to simplify them.

O(nlogn + n^1.01)

O(log (n^2))

My current idea is

O(nlogn + n^1.01) = O(nlogn)

O(log (n^2)) = O (log (n^2))

Please kindly help me on these two simplification problems and briefly give an explanation, thanks.

Answer 1

Remember:

log (x * y) = log x + log y

and n^k always grows faster than log n for any k>0.

Answer 2

For the second, you have O(lg(n²)) = O(2lg(n)) = O(lg(n)).

For the first, you have O(nlg(n) + n^(1.01)) = O(n(lg(n) + n^(0.01)), you've to decide whatever lg(n) or n^(0.01) grows larger.

For that purpose, you can take the derivative of n^0.01 - lg(n) and see if, at the limit for n -> infinity, it is positive or negative: 0.01/x^(0.99) - 1/x; at the limit, x is bigger than x^0.99, so the difference is positive and thus n^0.01 grows asymptotically faster than log(n), so the complexity is O(n^1.01).

Answer 3

Putting things together, for the first question O(n*log(n)+n^1.01) the first function grows faster than the second summand, i.e. since n*log(n) > n^1.01 for n greater than about 3, it is O(n*log(n))

In the second case use the formula mentioned by KennyTM, so we get

O(log(n^2)) = O(log(n*n)) = O(log(n)+log(n)) = O(2*log(n)) = O(log(n))

because constant terms can be ignored.