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
+1
A:
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).
Platinum Azure
2010-01-22 17:18:00
.. i already knew this the problem is that i can't find the c an k parameters even though i know they exist , that why i was asking for help
Giolo
2010-01-22 17:25:22
Trial and error is all you can do here. I'm serious.
Platinum Azure
2010-01-22 20:16:36
+1
A:
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.
Victor Nicollet
2010-01-22 17:21:36