Problem Detail: Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is $$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$ The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them. And with $g(n) = 3n^4$ we say $f(n)$ is $O(n^4)$. But what would Big-O be if instead of 3 we were given a really small constant, for example $$f(n) = 0.0000000001n^4 + 6n^3 + 10n^2 + 5n + 4$$ Would we still say $f(n)$ is $O(n^4)$?
Asked By : CodyBugstein
Answered By : usul
Medium answer – yes. As you said for the previous case, in the long run $n^4$ outpaces all of them. This is still true despite the constant in front. Check it out: plot. Also, remember that $n^3$ and $n^4$ are both $O(n^4)$, and in fact are both $O(n^{10})$ because big-O is an upper bound. So you might ask “is there any tighter big-O bound on this function than $O(n^4)$, like $O(n^3)$, and the answer would be no.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9002 Ask a Question Download Related Notes/Documents
