Algorithm analysis , Big O Notation Homework
Hi can someone explain me how to resolve this homework? (n + log n)3^n = O((4^n)开发者_开发百科/n). i think it's the same as resolving this inequality: (n + log n)3^n < c((4^n)/n)).
thanks in advance
You need to find a c (as you mentioned in your problem), and you need to show that the inequality holds for all n greater than some k.
By showing that you can find the c and k in question, then by definition you've proved the big-O bound.
Conversely, if you can't find such a c and k, this is because the function on the left is not really upper-bounded by the function on the right. That shouldn't be the case here, though (and you'll know you're getting a more intuitive understanding of asymptotic growth/bounding when you can articulate exactly why).
By definition, f(n) = O(g(n))
is true if there exists a constant M such that |f(n)| < M|g(n)|
for every n. In computer science, numbers are nonnegative, so this amounts to finding an M such that f(n) / g(n) < M
This, in turn, can be done by proving that f(n) / g(n)
has a finite limit as n
increases towards infinity (by definition of a limit). Which, in the case of your (n^2 + n log n) * (3/4)^n
is pretty obvious by virtue of how exponential functions work.
精彩评论