FInding top for f (n)
I am trying to understand programming concepts from the base. I came across two examples.
case1: find the upper bound f (n) = 3n + 8
It is very clear that f (n) → 3 as n-> infinity. Therefore, 3n + 8 must be less than or equal to 4n. So I can take c as 4.case2: Find the upper bound f (n) = n ^ 4 +100 (n ^ 2) +50
Here f (n) must be less than 2 (n ^ 4) for all n = 11. How do they come up with n = 11? I understand that a replacement will not be the best case.
It would be great if someone could explain the process of finding the upper bound.
source to share
This is a validation method, that is, a method of overriding or trickery.
They checked the condition when n^4 +100(n^2)+50
< 2*(n^4
).
Or, in other words n^4 > (100 * n^2 + 50)
.
When you solve for it, the result is 11.
That is, for n> = 11. n^4 +100(n^2)+50
< 2*(n^4)
.
It's not easy to calculate, you can find it with Wolfram Alpha.
It can also be solved by solving the inequality for the value n.
n^4 > (100 * n^2 + 50)
n^4 - 100 * n^2 - 50 > 0
// find the roots for this equation and then
// you'll be easily able to deduce the value of n using wavy-curve method.
Check here how to solve the inequality using the wave curve method , but for that you will need to find the value for n that solves the given equation.
source to share