math - What is the Big O of "n + log?log?(n^2)"?

Question

Hello everyone my question is that what is the big O of n + loglog(n^2) and why?

I think it should be O(n) but my teacher just told me that my answer is wrong... can someone explain to me why?

question from:https://stackoverflow.com/questions/65911089/what-is-the-big-o-of-n-loglogn2

Answer 1

Your answer O(n) is correct. Google logarithm rules (easy to forget if you don't use it often) and find in particular the power law and the multiplication law. By applying the power law first and then the multiplication law we can reduce your equation like this:

I have used Wolfram Alpha to quickly plot the reduced version:

If you 'zoom out' a little bit as presented on the second graph you can see that the function behaves as a logarithm (up to X = 2 roughly) and linear for X > 2. This is why in big O notation we say that the linear term n is dominant over the logarithm in this case as it is of the highest power and dictates the algorithm scaling behavior.