I was wondering if I am using these rules in a valid way. Lets say I had a question involving the common factor rule and log dom rule. If I had to prove that
( 15 * n^2 * log n ) exists in O( n^2 )
By common factor rule I know we can say that
( n^2 * log n ) exists in O( n^2 * log n)
I also say by log domination that
( n^2 * log n ) exists in O( n^2 )
I'm not sure if that last step is correct or not. I know log n is always going to be in the O(n), it is always smaller. But can I say n^2*log n exists in O(n^2) based on the same principle?
The rules:
Constant factor rule
k*f(n) exists in O(f(n)) for all constants K > 0
Log Dom Rule
(log^k n) exists in O(n^t) for all k, t > 0
You cannot say that $n^2\log(n)$ exists in $O(n^2)$ since there is no constant $k$ such that $n^2\log(n) < kn^2$ for all $n > N$. Suppose there was such a $k$, then if you choose $n = k^k$, you have
$$n^2\log(n) = (k^k)^2\log(k^k) $$ $$(k^k)^2\log(k^k) = k(k^k)^2\log(k)$$ $$k(k^k)^2\log(k) > k(k^k)^2$$
We can say that $n^2\log(n)$ exists in $O(n^2\log(n))$ or also that it exists in $O(n^3)$.