Simple Big O with lg(n) proof
algorithm, big-o
Solution
For any base b, we know that there always exists an `n0 > 0` such that
`log(n)/log(b) < n` whenever `n >= n0`
Thus,
`n^3 - 7n^2 + nlg(n) + 10` < `n^3 - 7n^2 + n^2 + 10` when `n >= n0`.
You can solve from there.
Problem
I'm attempting to guess and prove the Big O for: f(n) = n^3 - 7n^2 + nlg(n) + 10 I guess that big O is n^3 as it is the term with the largest order of growth However, I'm having trouble proving it. My unsuccesful attempt follows: ``` f(n) <= cg(n) f(n) <= n^3 - 7n^2 + nlg(n) + 10 <= cn^3 f(n) <= n^3 + (n^3)*lg(n) + 10n^3 <= cn^3 f(n) <= N^3(11 + lg(n)) <= cn^3 so 11 + lg(n) = c ``` But this can't be right because c must be constant. What am I doing wrong?