# Thread: Need help with Growth of Functions questions

1. ## Need help with Growth of Functions questions

I've never really gotten the hang of algorithms and the like, so I could really use a hand with these.

Here's the question, word for word. Be sure to show your work.

Determine whether or not the following are true. Provide a derivation showing why or why not. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation.

a) $99$ is $\Theta(1)$

b) $6n^3-3n^2\log n-6n^2+11n\log n$ is $\Omega(n^3)$

c) $7n^2-19n+32$ is $O(n^3)$

d) $n^5/44 -3n^4$ is $\Theta(n^4)$

2. Originally Posted by Runty
I've never really gotten the hang of algorithms and the like, so I could really use a hand with these.

Here's the question, word for word. Be sure to show your work.

Determine whether or not the following are true. Provide a derivation showing why or why not. For convenience, you may assume that the logs are in the base of your choice, but you should specify what base you are using in your derivation.

a) $99$ is $\Theta(1)$

b) $6n^3-3n^2\log n-6n^2+11n\log n$ is $\Omega(n^3)$

c) $7n^2-19n+32$ is $O(n^3)$

d) $n^5/44 -3n^4$ is $\Theta(n^4)$
c) $7n^2-19n+32$ is $O(n^3)$

Definition of big O notation:

$f(x)=O(g(x)) \text{ as } x\to\infty\,$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that
$|f(x)| \le M |g(x)| \text{ for all }x>x_0.$

Let $f(x) = 7x^2-19x+32, g(x) = x^3$. For $x = 10, f(x) = 542, g(x) = 1000$, and since $f(x) \le g(x) \text{ for all }x>10$, take $x_0 = 10, M = 1$ and you've proved $7n^2-19n+32$ is $O(n^3)$.

The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.

3. Originally Posted by lgstarn
Let me know if you have questions about any one of the four definitions or need another example.
By four definitions I mean Omega, little o, big O, or Theta.

4. Originally Posted by lgstarn
c) $7n^2-19n+32$ is $O(n^3)$

Definition of big O notation:

$f(x)=O(g(x)) \text{ as } x\to\infty\,$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that
$|f(x)| \le M |g(x)| \text{ for all }x>x_0.$

Let $f(x) = 7x^2-19x+32, g(x) = x^3$. For $x = 10, f(x) = 542, g(x) = 1000$, and since $f(x) \le g(x) \text{ for all }x>10$, take $x_0 = 10, M = 1$ and you've proved $7n^2-19n+32$ is $O(n^3)$.

The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.
SECOND EDIT: Ugh, I just can't be sure whether or not this would truly work. The main problem is either my sources not explaining themselves or me misinterpreting the examples I'm finding. I still need help on these.

5. Originally Posted by Runty
a) $99$ is $\Theta(1)$
Definition of $\Theta$

$f(x)=\Theta(g(x)) \text{ as } x\to\infty\,$ if and only if there exists positive real numbers $k_1$ and $k_2$ and a positive real number $x_0$ such that

$k_1|g(x)| \le |f(x)| \le k_2 |g(x)| \text{ for all }x>x_0$

$f(x) = 99, g(x) = 1$

Thus $k_1 = 98, k_2 = 100$ for any $x_0$, say $x_0 = 42$.

Originally Posted by Runty
b) $6n^3-3n^2\log n-6n^2+11n\log n$ is $\Omega(n^3)$
$f(x)=\Omega(g(x)) \text{ as } x\to\infty\,$ if and only if there exists s positive real number $k_1$ and a positive real number $x_0$ such that

$k_1|g(x)| \le |f(x)| \text{ for all }x>x_0$

$f(x) = 6n^3-3n^2\log n-6n^2+11n\log n$

$g(x) = n^3$

$f(10) = 5353.28$
$g(10) = 1000$

We can now see that $f(x)$ is growing faster than $g(x)$ for $x > 10$. It is probably enough to just say that because it is pretty obvious if you look at it. But if your teacher is feeling pedantic, you can try to show it in a couple of ways.

Way number 1: plot the function $h(x) = f(x) - g(x) = 5x^3-3x^2\log x-6x^2+11x\log x$ and show it is always positive for $x > 2$. Thus, $f(x)$ grows faster than $g(x)$. But maybe your teacher doesn't like a graphical "proof."

Way number 2: Consider $\lim_{x \rightarrow \infty} \frac{6x^3-3x^2\log x-6x^2+11x\log x}{x^3} = 6$, thus $f(x)$ asymptotically grows 6 times faster than $g(x)$. But maybe your teacher will say, but how do you know that is valid for $x > 10$ and not $x > 100$?

Way number 3: Call $h(x) = f(x) - g(x)$ and compute $h'(x) = 15x(x-1) + (11 -6x)\log(x) + 11$. Notice that $\log(x)$ grows really slowly (say it is $\log_{10}(x)$, so $\log_{10}(10) = 1$), and so clearly $h'(x) > 0$ for $x > 10$. So $h(x)$ is growing, and thus $f(x)$ is growing faster than $g(x)$. But again I relied on the fact that one function is 'clearly' growing faster than another.

Anyways, I doubt your teacher wants you to go to this level of detail unless it is an excessively mathematical class. Just saying it grows faster should be enough.

While this stuff looks complicated, it is actually really simple. You can use this ordering to get a really intuitive feel for this:

Big O notation - Wikipedia, the free encyclopedia

to quickly understand which functions grow from slowest to fastest, from a constant all the way up to factorials and iterated exponential.

So anyways, why don't you give $n^5/44 -3n^4$ is $\Theta(n^4)$ a try for yourself?

6. I feel I should iterate: for solving these, you must use either the inequalities method or the limits method.

I suppose your answers could work, but I feel as though I need a second opinion.

EDIT: Also, I feel I could use some help on the last one, $n^5/44 -3n^4$. I know it's not $\Theta(n^4)$, but I could use some help with a proof.

7. Originally Posted by lgstarn
c) $7n^2-19n+32$ is $O(n^3)$

Definition of big O notation:

$f(x)=O(g(x)) \text{ as } x\to\infty\,$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that
$|f(x)| \le M |g(x)| \text{ for all }x>x_0.$

Let $f(x) = 7x^2-19x+32, g(x) = x^3$. For $x = 10, f(x) = 542, g(x) = 1000$, and since $f(x) \le g(x) \text{ for all }x>10$, take $x_0 = 10, M = 1$ and you've proved $7n^2-19n+32$ is $O(n^3)$.

The rest of these are really similar. Put in the definitions and find some constants that satisfy the definition. Let me know if you have questions about any one of the four definitions or need another example.

I get that from that equation the big O would be $n^2$ could you future elaborate how big o is $O(n^3)$