Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding the upper bound of a mathematical function (function analysis)

I am trying to understand Big-O notation through a book I have and it is covering Big-O by using functions although I am a bit confused. The book says that O(g(n)) where g(n) is the upper bound of f(n). So I understand that means that g(n) gives the max rate of growth for f(n) at larger values of n.

and that there exists an n_0 where the rate of growth of cg(n) (where c is some constant) and f(n) have the same rate of growth.

But what I am confused is on these examples on finding Big O in mathmatical functions.

This book says findthe upper bound for f(n) = n^4 +100n^2 + 50 they then state that n^4 +100n^2 + 50 <= 2n^4 (unsure why the 2n^4) then they some how find n_0 =11 and c = 2, I understand why the big O is O(n^4) but I am just confused about the rest.

This is all discouraging as I don't understand but I feel like this is an important topic that I must understand.

If any one is curious the book is Data Structures and Algorithms Made Easy by Narasimha Karumanchi

Not sure if this post belongs here or in the math board.

like image 797
Jude Avatar asked May 29 '16 02:05

Jude


People also ask

How do you find the upper bound of a function?

If you divide a polynomial function f(x) by (x - c), where c > 0, using synthetic division and this yields all positive numbers, then c is an upper bound to the real roots of the equation f(x) = 0. Note that two things must occur for c to be an upper bound. One is c > 0 or positive.

How do you find the upper bound in real analysis?

A set A ⊂ R of real numbers is bounded from above if there exists a real number M ∈ R, called an upper bound of A, such that x ≤ M for every x ∈ A. Similarly, A is bounded from below if there exists m ∈ R, called a lower bound of A, such that x ≥ m for every x ∈ A.


1 Answers

Preparations

First, lets state, loosely, the definition of f being in O(g(n)) (note: O(g(n)) is a set of functions, so to be picky, we say that f is in O(...), rather than f(n) being in O(...)).

If a function f(n) is in O(g(n)), then c · g(n) is an upper bound on f(n), for some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e. , n ≥ n0 for some constant n0).

Hence, to show that f(n) is in O(g(n)), we need to find a set of constants (c, n0) that fulfils

f(n) < c · g(n), for all n ≥ n0,                                (+)

but this set is not unique. I.e., the problem of finding the constants (c, n0) such that (+) holds is degenerate. In fact, if any such pair of constants exists, there will exist an infinite amount of different such pairs.


Showing that f ∈ O(n^4)

Now, lets proceed and look at the example that confused you

Find an upper asymptotic bound for the function

f(n) = n^4 + 100n^2 + 50                                      (*)

One straight-forward approach is to express the lower-order terms in (*) in terms of the higher order terms, specifically, w.r.t. bounds (... < ...).

Hence, we see if we can find a lower bound on n such that the following holds

100n^2 + 50 ≤ n^4, for all n ≥ ???,                             (i)

We can easily find when equality holds in (i) by solving the equation

m = n^2, m > 0

m^2 - 100m - 50 = 0
(m - 50)^2 - 50^2 - 50 = 0
(m - 50)^2 = 2550
m = 50 ± sqrt(2550) = { m > 0, single root } ≈ 100.5

     => n ≈ { n > 0 } ≈ 10.025

Hence, (i) holds for n ≳ 10.025, bu we'd much rather present this bound on n with a neat integer value, hence rounding up to 11:

100n^2 + 50 ≤ n^4, for all n ≥ 11,                              (ii)

From (ii) it's apparent that the following holds

f(n) = n^4 + 100n^2 + 50 ≤ n^4 + n^4 = 2 · n^4, for all n ≥ 11, (iii)

And this relation is exactly (+) with c = 2, n0 = 11 and g(n) = n^4, and hence we've shown that f ∈ O(n^4). Note again, however, that the choice of constants c and n0 is one of convenience, that is not unique. Since we've shown that (+) holds for on set of constants (c,n0), we can show that it holds for an infinite amount of different such choices of constants (e.g., it naturally holds for c=10 and n0=20, ..., and so on).

like image 50
dfrib Avatar answered Oct 15 '22 15:10

dfrib