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

1 answer

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.



All Articles