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.