whats is the big O notation of this function f(x) = logn + 3n i have ridden big o notation but i am confuse in this function so please help me
Asked
Active
Viewed 1,263 times
2
-
2Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – sertsedat Jun 05 '18 at 13:13
-
2This should just be overall `O(n)`, since at large `n` values, the `3n` term will dominate. – Tim Biegeleisen Jun 05 '18 at 13:14
-
hello @TimBiegeleisen but the answer in book is O(log n) that's why i am confuse – shashank singh bisht Jun 05 '18 at 13:17
2 Answers
2
It is simply O(n).
When you have a composite of multiple parts in big O notation which are added, you have to choose the biggest one. In this case it is O(3n), but there is no need to include constants inside parentheses, so we are left with O(n).
Islam Murtazaev
- 1,488
- 2
- 17
- 27
0
It's O(n).
Proof: lim n->inf f(n)/3n = lim n->inf (logn + 3n) / 3n = [0 + 1] = 1
so f(n) and 3n have the same asimptotic behavior
according to the "O" notation constants are dropped so f(n) is O(3n) = O(n)
Alessio Corrado
- 1
- 1