Why log(n) + n = O(n) instead O(logn)
Can someone explain?
Hi @Virag_Shukla,
This is Fatimah Abdullah from Educative.
To answer your question, let’s iterate back to the lesson discussing the Asymptotic Analysis. We need to consider that on which factor the growth rate of the function f(n) = log(n) + n depends.
| f(n) = n | f(n) =log(n) |
|---|---|
| n = 1 | log(n) = 0 |
| n = 5 | log(n) = 0.69897 |
| n = 10 | log(n) = 1 |
| n = 20 | log(n) = 1.30103 |
| n = 30 | log(n) = 1.47712 |
| n = 40 | log(n) = 1.60206 |
As you can see, the growth rate of f(n) = n is much greater than f(n)= log(n). Therefore, we will only consider the larger of the two. In the lesson “Introduction to Asymptotic Analysis and Big O” you will find a table that lists the growth rates of different functions in ascending order. I hope this helps clear your confusion.
We hope Educative has inspired to further your learning, and please drop us a note if you have any other questions or concerns.
Best Regards,
Fatimah Abdullah | Developer Advocate
Educative Inc.