presenting the definitions from the course notes and example for all definitions with some graphs to get a good visualization of what the definition means.
Lets assume we have a function f(n) = 3n^2 - 2n + 5 and g(n) =
4n^3 + n^2 - 3n + 3
for all definitions below.
The Definition of Big-Oh
The claim is f(n) is in O(g(n))? We can show this by making a graph of the two functions and then seeing if we need to multiply g(n) by a constant to make it true for any natural number >= B.
red is f(n)purple is g(n)
As you can see the behavior if we were to continue this graph far to the right as much as possible we can predict that the function f(n) will never be able catch up to g(n) after they intersected at a point which could be our break point however it must be of the domain of natural numbers, therefore the intersections are not always considered the break point and both the break point B and the constant c are dependent on each other and could vary on our choice of either one. However the intersection tells us that the B could be any natural number from that point and on wards. The key point to this graph is that f(n) is bounded above by c*g(n) for any natural number n equal to or greater then the B, break point.
The Definition of Big - Omega
red is f(n)
purple is g(n)
As you can see it looks possible for f(n) can also be >= to c*g(n) where c is a rational number with a significantly greater denominator such as (1/1000) which will cause c*g(n) to never catch up however if we looked at the graph with a bigger scale we will notice an intersection of the two graphs which indicates f(n) will not always be in Big-Omega of g(n) as n approaches infinity therefore
The claim is False
If this seems wrong or if I possibly misunderstood some of the content please leave me a comment and let me know? Also Note, assuming both examples above were True we can also say f(n) is in Theta of g(n)
Thanks for reading
No comments:
Post a Comment