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)$).

| cite | improve this answer | |

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.