I have an expression $$n\frac{10\log(n)+O(n)+4n}{O(n)+n\log(n)}$$ and I am not really sure about ${O(n)+n\log{(n)}}$ part. If I am adding $O(n)$, pr $O(n^2)$, $O(n\log n$ etc., to function $n\log(n)$, or $n^2$, $n$ etc. Are there same rules as for two big O-notation functions. Should I use bigger one with O-notation so $O(n\log n)$?
Asked
Active
Viewed 137 times
2 Answers
1
Yes, this is so: $$O(n)+n\log{n}=O(n\log{n})$$ To see this, let $f(n)$ be $O(n)$. Then, by definition, there exists a constant $c$ and a $n_0$ such that $$f(n)\le c\cdot n$$ for all $n\ge n_0$. However, this implies that $$f(n)\le c\cdot n\le c\cdot n\cdot \log n$$ (since $\log {n}\ge 1$ for $n\ge2$, assuming basis is $2$) and hence $$f(n)=O(n\log{n})$$ as well.
Jimmy R.
- 35,868
1
Technically speaking, the expression
$$n\frac{10\log(n)+O(n)+4n}{O(n)+n\log(n)}$$ is meaningless because $O(n)$ denotes any function that grows not slower than $n$. So this ratio has no particuliar value nor specific asymptotic behavior (not counting the fact that the two $O$'s might denote different functions).
A common misconception about $O(f(n))$ is that it denotes a function that is "approximately $f(n)$". This is wrong.