# 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) $\displaystyle 99$ is $\displaystyle \Theta(1)$

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

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

d) $\displaystyle n^5/44 -3n^4$ is $\displaystyle \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) $\displaystyle 99$ is $\displaystyle \Theta(1)$

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

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

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

Definition of big O notation:

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

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

Definition of big O notation:

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

Let $\displaystyle f(x) = 7x^2-19x+32, g(x) = x^3$. For $\displaystyle x = 10, f(x) = 542, g(x) = 1000$, and since $\displaystyle f(x) \le g(x) \text{ for all }x>10$, take $\displaystyle x_0 = 10, M = 1$ and you've proved $\displaystyle 7n^2-19n+32$ is $\displaystyle 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) $\displaystyle 99$ is $\displaystyle \Theta(1)$
Definition of $\displaystyle \Theta$

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

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

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

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

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

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

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

$\displaystyle g(x) = n^3$

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

We can now see that $\displaystyle f(x)$ is growing faster than $\displaystyle g(x)$ for $\displaystyle 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 $\displaystyle h(x) = f(x) - g(x) = 5x^3-3x^2\log x-6x^2+11x\log x$ and show it is always positive for $\displaystyle x > 2$. Thus, $\displaystyle f(x)$ grows faster than $\displaystyle g(x)$. But maybe your teacher doesn't like a graphical "proof."

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

Way number 3: Call $\displaystyle h(x) = f(x) - g(x)$ and compute $\displaystyle h'(x) = 15x(x-1) + (11 -6x)\log(x) + 11$. Notice that $\displaystyle \log(x)$ grows really slowly (say it is $\displaystyle \log_{10}(x)$, so $\displaystyle \log_{10}(10) = 1$), and so clearly $\displaystyle h'(x) > 0$ for $\displaystyle x > 10$. So $\displaystyle h(x)$ is growing, and thus $\displaystyle f(x)$ is growing faster than $\displaystyle 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 $\displaystyle n^5/44 -3n^4$ is $\displaystyle \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, $\displaystyle n^5/44 -3n^4$. I know it's not $\displaystyle \Theta(n^4)$, but I could use some help with a proof.

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

Definition of big O notation:

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

Let $\displaystyle f(x) = 7x^2-19x+32, g(x) = x^3$. For $\displaystyle x = 10, f(x) = 542, g(x) = 1000$, and since $\displaystyle f(x) \le g(x) \text{ for all }x>10$, take $\displaystyle x_0 = 10, M = 1$ and you've proved $\displaystyle 7n^2-19n+32$ is $\displaystyle 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 $\displaystyle n^2$ could you future elaborate how big o is $\displaystyle O(n^3)$