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
-
do you want an answer? You won't get that here. All you will get is perhaps some advice on how to approach it.wheaties– wheaties2010-01-22 17:17:01 +00:00Commented Jan 22, 2010 at 17:17
-
Do you have a specific question? Or just, "Here's my homework, please do it for me?"BlueRaja - Danny Pflughoeft– BlueRaja - Danny Pflughoeft2010-01-22 17:17:31 +00:00Commented Jan 22, 2010 at 17:17
Add a comment
|
2 Answers
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).
1 Comment
Giolo
.. 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
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.
1 Comment
Giolo
you mean doing : lim n--> infinity of (n^2+nlogn)* 3^n / (4^n) ?