so I just had this question, I know that for example $g(n) = 100$, then $O\big(g(n)\big) = O(1)$. Let us take $a(n)$ as some function like $n\log n$, does this mean that $a(n)\in O\big(g(n)\big)$?
Asked
Active
Viewed 30 times
0
-
Your question is missing clarity. – Oct 27 '20 at 19:12
-
Are you asking whether $n \log n \in O(100)$? – Misha Lavrov Oct 27 '20 at 19:15
1 Answers
1
So you have $g(n) = 100$, in which case $g(n)$ is $O(1)$. You then define $a(n) = n\log n$ and ask if $a(n)$ is $O(g(n))=O(1)$.
The answer is no.
For $a(n)$ to be $O(1)$, it would have to be true that $n\log n$ was bounded by a constant from some point and onwards, but $n\log n$ grows to infinity, making such a bound impossible.
Mankind
- 13,170
-
-
For a positive function $a(n)$ to be bounded by a constant (from some point and onwards) means that there exists a real number $C>0$, such that $a(n) < C$ for all sufficiently large $n$ - i.e. that there is a constant $C>0$ such that all values of $a(n)$ are smaller than $C$ from some $n$. – Mankind Oct 27 '20 at 22:26