# How to determine if given “complex” time complexity is $O(n^2)$?

If a given time complexity, such as these:

1. $$(n + \log n) * \sqrt{n+\log n}$$
2. $$n * (200 + \log^2 n)$$
3. $$(7+n^3)\log(n^5)$$

is not determinable by just looking at it whether is it in class $$O(n^2)$$ or not, how do I decide? If a time complexity is given, and in it there are more types of expressions (exponential, logarithmic, polinomial, ... ) how do I decide which one determines the $$O(n^2)$$ or $$O(n\log n)$$ or ... complexity?

Sometimes, you can replace them by $$n$$. For example, in $$F_1(n) = (n+\log(n))\times \sqrt{n+\log n}$$, replace $$\log(n)$$ by $$n$$. So, $$F_1(n) \leqslant 2n \sqrt{2n}$$ and it means $$F_1(n) = O(n\sqrt{n})$$. Also, in multiplication or summation, you can ignore constants (not all the time in power functions). Hence, $$F_2(n) = n \times (200 + \log^2(n)) = \Theta(n \log^2(n))$$. Or in $$F_3(n) = (7 + n^3) \log(n^5) = 5 \times (7 + n^3) \log(n) = \Theta(n^3 \log(n))$$ (as $$\log(n^c) = c \log(n)$$).

I have a non-rigorous approach which might be of help:

If your expression is really hard to simplify, you can try guessing the fastest growing term (although sometimes even then it's not that obvious).

Taking your first function as an example, we can easily guess that $$f(n) \in O(n\sqrt{n})$$ (see OmG's way). Now, you can simply choose some large $$n$$, say, $$10^6$$, and see if $$f(n) \le c \cdot n\sqrt{n}$$ for some constant $$c$$, say, $$5$$. This can be done using Python which can handle large numbers pretty well (see this answer).

Here's an example code:

import math

def f(n):
return (n + math.log2(n)) * math.sqrt(n + math.log2(n)) # your first function
n = 1000000
c = 5
print(f(n) <= c * n**(1.5)) # prints True



Note that this is a similar question to this, but I couldn't say that in a comment because I don't have enough reputation.