Math/CS Question (looking at Yoni..)

[iago]

Ok, I was talking about this in channel earlier, but Yoni went and died or something, so here's my problem:

This is the definition of theta-notation:

Formal Definition: f(n)=theta(g(n)) iff there exists positive constants c1, c2, and n0 such that c1*g(n) <= f(n) <= c2*g(n) for all n, n>=n0.

-http://hebb.cis.uoguelph.ca/~dave/27242/notes/analysis.html

Now here's a question from my last assignment:
Find and prove the theta of the following:
b) 3n + log(n³ + n² + 2) + 35



And while I'm asking stuff:
Find the following limit by first finding the log of the expression, doing the limit, and then exponentiating:

I know how to find this limit normally (it's 1), but what about the way that he's requesting?



One last thing, this assignment is old, I'm just trying to figure out what I did wrong before the midterm, so I'm not looking for free answers.

[haZe]

just a guess...im in 6th grade so its prob wrong =p
731?   cuz i figure 3 to the third which gives u 27 to the second plus 35 gave me 731.
:-/

[Zakath]

n is a variable...don't know if it's 3 or not

[Yoni]

Informally,

lim [n->+infinity] ( (1+(1/n)) / (1-(1/n)) )^n =

= lim [n->+infinity] e^ln( ( (1+(1/n)) / (1-(1/n)) )^n ) =

= lim [n->+infinity] e^(n * ln( (1+(1/n)) / (1-(1/n)) )) =

= e^(n * ln(1)) = e^0 = 1

[Yoni]

As for the first question, it seems like your definition of theta is loose, that is, a theta of a function is not unique. If this is true, there is no relevance to a discussion about "the theta" of a given function.

[iago]

As for the first question, it seems like your definition of theta is loose, that is, a theta of a function is not unique. If this is true, there is no relevance to a discussion about "the theta" of a given function.

Ah, that makes so much sense, your first answer.  And yes, theta is not unique, however there is a best answer, if I'm right.

[Yoni]

What is the definition of a best theta?

[iago]

Hmm.. I think it boils down to this question:
Given a function, say, f(x) = x² + 6x + 1, prove that g(x) = Cx² is greater than f(x) for all x greater than some n, for some value of c.  

In other words, pick a C, pick n, and prove that g(x) > f(x) for the entire range -> infinity.

I probably should know how to do that already, but I forget most of what I learned about math.

[Etheran]

Yoni's math forum gogogo

[Yoni]

The question of how to pick such a "best" function remains.
If you want Cx² to be greater than x²+6x+1 from some starting value to infinity, you can pick any C>1 for that. C=1 itself cannot be picked. The catch is that the closer you go to C=1, the bigger the starting value would have to be. For example if you use g(x)=1.0000001x², the functions meet at:

f(x) = g(x)
x²+6x+1 = 1.0000001x²
0.0000001x² - 6x - 1 = 0
x² - 60000000x - 10000000 = 0
x =~ 60000000.16666666620370370627572
(negative value for x omitted)

Since you can theoretically continue this endlessly I don't see how to pick the "best" theta.

Thinking about it logically, the "best" theta would be one for which the "cost" for making C as small as possible is chosen to get the most efficient "cost" for making the starting value as small as possible (i.e. their sum is a minimum, or whatever), which can be solved using calculus depending on the rule you picked.

Btw, how did you pick g(x)=Cx²? How would you pick such a g(x) for your original question, 3n+log(n³+n²+2)+35?

[iago]

Btw, how did you pick g(x)=Cx²? How would you pick such a g(x) for your original question, 3n+log(n³+n²+2)+35?

I picked the biggest term in the first question, but I would have no idea how to pick one for the 3n+log(n³+n²+2) one.

Now, how do you PROVE that x² is an acceptable g(x) for a certain value of n?  

hmm.. I think I see, now, just do what you did to find the 1 and the 6000000, but make it an inequality.  But say you make g(x)=x, and f(x)=x²+6x+1.  This is not a valid g(x), right?  And how would I prove that?

Thinking about it logically, the "best" theta would be one for which the "cost" for making C as small as possible is chosen to get the most efficient "cost" for making the starting value as small as possible (i.e. their sum is a minimum, or whatever), which can be solved using calculus depending on the rule you picked.

Yes, I see how that would be possible using min/max and all the fun stuff (find the min of n0 + c, and all that), but we don't have to go that far.  I think any value of c and n0 will due, as long as it can be proven that it's valid on [n0,inf).

[Yoni]

Oh, ok then.

For f(x) = x²+6x+1 I would pick g(x) = 2x².
Then:

g(x) > f(x)
2x² > x²+6x+1

x² - 6x - 1 > 0
[ x > 3+sqrt(10) ] or [ x < 3-sqrt(10) ]

So for all x>3+sqrt(10), 2x²>x²+6x+1.

For f(n) = 3n+log(n³+n²+2)+35:

For sufficiently large values of n, in the expression n³+n²+2 the "n²+2" part doesn't "contribute" much, since the n³ is sufficiently much larger than it.
The same goes for the constant +35.

Thus for sufficiently large n:
[3n + log(n³ + n² + 2) + 35] ~ [3n + log(n³)] = 3n + 3log(n)

In calculus you learn that log(x) ascends much "slower" than x. So for sufficiently large n, the 3log(n) is also dismissable.

So for large n, the most "important" factor of f(n) is 3n.
So: g(n) = Cn for any C>3.

Assuming g(n) = 4n is picked:

g(n) > f(n)
4n > 3n+log(n³+n²+2)+35
4n / [3n+log(n³+n²+2)+35] > 1

lim [n->+infinity] 4n / [3n+log(n³+n²+2)+35] =
(*)
= lim [n->+infinity] 4 / [3+(3n²+2n)/(n³+n²+2)] =

= lim [n->+infinity] 4 / [(3n³+6n²+2n+6)/(n³+n²+2)] =

= lim [n->+infinity] (4n³+4n²+8)/(3n³+6n²+2n+6) =

= 4/3

(*) L'Hopital's rule.

lim [n->+infinity] g(n)/f(n) = 4/3

If you really want to go formal, this means:
"For any epsilon>0, there exists some n0 so that for all n>n0, |g(n)/f(n) - 4/3| < epsilon"

If we pick epsilon = 1/3:
There exists some n0 so that for all n>n0, |g(n)/f(n) - 4/3| < 1/3

-1/3 < g(n)/f(n) - 4/3 < 1/3

1 < g(n)/f(n) < 5/3

g(n)/f(n) > 1

g(n) > f(n) for all n>n0. Q.E.D.

Note that using rigorous infinitesimal math definitions hides the value of n0. You might have to do some more testing/mathematical expansion to get this one but n0=100 looks promising. (This is not, of course, the minimal n0, which you would have to use calculus to find.)

[iago]

It's all coming together!  I think I know enough to do most questions, and he promised not to put any difficult questions on our midterm (it's only 50mins long).  And half of it is about recursive stuff, which was much better documented in our notes than the stuff I was asking about.

One final question - what's Q.E.D. stand for?

edit - Also, thanks Yoni!

[Yoni]

Quod erat demonstrandum. (Yes, I remembered this, not looked it up just now.)

Slightly more info: http://mathworld.wolfram.com/QED.html

[iago]

eew, latin!

Hah, I just did the exam, the only question on that was, "is f(x) an element of O(g(x)), or g(x) an element of o(f(x))?"  And a bunch've questions with nothing more complicated than nlogn vs. n*sqrt(n) in them, so that was good.  Some nasty questions on recursion, but I think I still did OK.