Big Oh in arithmetic expression

tasos · #1 $Old$ 11-10-2008, 05:15 AM

Hello to everyone,

Could somebody please tell me how do we solve exercises like the one I describe below:

$exp(1+(O(1/n))^2)$ = e + O(1/n)

Thanks a lot,
Tasos

mmm4444bot · #2 $Old$ 11-10-2008, 05:29 AM

Hi Tasos:

I see the equation, but I do not know what the instructions are for this exercise.

Are exp(1) and e both the same constant in this equation?

What are we to do with this equation?

~ Mark

tasos · #3 $Old$ 11-10-2008, 05:34 AM

First of all, I want to thank you mmmbot for answering.

Sorry if I didn't write it well. By writing exp I meant e to the power.

So I mean: [e to the power of (1 + (O(1/n))^2)] = e + O(1/n)

P.S.1: Could you tell me how to write it in the post so as it will appear correctly?
P.S.2: What you say is right: exp(1) and e are the same thing. That is what I mean.

mmm4444bot · #4 $Old$ 11-10-2008, 05:36 AM

I read it as follows.

e^[1 + (O/n)^2] = e + O/n

tasos · #5 $Old$ 11-10-2008, 05:44 AM

Quote:

Originally Posted by mmm4444bot $View Post$

I read it as follows.

e^[1 + (O/n)^2] = e + O/n

Sorry, then. I didn't write O/n, but O(1/n).

Is it the same thing?

mmm4444bot · #6 $Old$ 11-10-2008, 05:53 AM

I'm checking to see whether or not O(1/n) is function notation ... be right back.

A big "Oh, please excuse me".

I thought O and n were constants. (I just saw the big Oh function for the first time at Wikipedia.)

No, you are correct. O(1/n) is good.

I cannot help you with this exercise.

Now, I read it as follows.

e^[1 + O(1/n)^2] = e + O(1/n)

Again, sorry for goofing up your thread.

~ Mark

tasos · #7 $Old$ 11-10-2008, 06:04 AM

Quote:

Originally Posted by mmm4444bot $View Post$

I'm checking to see whether or not O(1/n) is function notation ... be right back.

A big "Oh, please excuse me".

I thought O and n were constants. (I just saw the big Oh function for the first time at Wikipedia.)

No, you are correct. O(1/n) is good.

I cannot help you with this exercise.

Now, I read it as follows.

e^[1 + O(1/n)^2] = e + O(1/n)

Again, sorry for goofing up your thread.

~ Mark

No problem, Mark. Don't worry.

Laurent · #8 $Old$ 11-10-2008, 01:36 PM

Quote:

Originally Posted by tasos $View Post$

Hello to everyone,

Could somebody please tell me how do we solve exercises like the one I describe below:

$exp(1+(O(1/n))^2)$ = e + O(1/n)

Thanks a lot,
Tasos

Are you sure you put the parentheses at the right place? Because this is correct, but not optimal, as you shall see:

I'll apply usual properties of the "big O" notation. If you don't know them, just ask, the proofs are very short.
First you have $\left(O\left(\frac{1}{n}\right)\right)^2=O\left(\frac{1}{n^2}\right)$ , and it is more usual to write it this way.
Then $e^{1+O\left(\frac{1}{n^2}\right)}=e e^{O\left(\frac{1}{n^2}\right)}= e\left( 1+O\left(\frac{1}{n^2}\right)\right)$ $=e + e\, O\left(\frac{1}{n^2}\right)=e+O\left(\frac{1}{n^2}\right)$ .
I used the following expansion of the exponential at 0: $e^{O(u)}=1+O(u)$ when $u$ tends to 0, composed with the sequence $\left(\frac{1}{n^2}\right)_n$ which tends to 0.

Now, $0\leq\frac{1}{n^2}\leq \frac{1}{n}$ , hence the previous big O can be replaced by $O\left(\frac{1}{n}\right)$ , and this is what you need.

Let us now suppose that the question was $e^{\left(1+O\left(\frac{1}{n}\right)\right)^2}=1+O\left(\frac{1}{n}\right)$ , which seems more plausible to me.
Then we would have: $\left(1+O\left(\frac{1}{n}\right)\right)^2=1+O\left(\frac{1}{n}\right)+O\left(\frac{1}{n^2}\right)=1+O\left(\frac{1}{n}\right)$ (as before, the second big O can be included in the first one), and by the same computation as above we conclude $e^{\left(1+O\left(\frac{1}{n}\right)\right)^2}=e+O\left(\frac{1}{n}\right)$ .

ps: about the way to write symbols, there's a section in the forum related to "LaTeX", and this is where you should look for help about this.

tasos · #9 $Old$ 11-10-2008, 04:44 PM

Thank you very much Laurent for your answer. It is very thorough.

However, I have a little question.

How do you go from the left part to the right one in the following expression:

Quote:

Originally Posted by Laurent $View Post$

$e e^{O\left(\frac{1}{n^2}\right)}= e\left( 1+O\left(\frac{1}{n^2}\right)\right)$

Thanks

Laurent · #10 $Old$ 11-11-2008, 04:57 AM

Quote:

Originally Posted by tasos $View Post$

Thank you very much Laurent for your answer. It is very thorough.

However, I have a little question.

How do you go from the left part to the right one in the following expression:
Thanks

This is because of this result:

Quote:

Originally Posted by Laurent $View Post$

I used the following expansion of the exponential at 0: $e^{O(u)}=1+O(u)$ when $u$ tends to 0, composed with the sequence $\left(\frac{1}{n^2}\right)_n$ which tends to 0.

In fact, as soon as a function $f$ is differentiable at $0$ , we have $f(x)=f(0)+O(x)$ as $x$ tends to 0 (because $\frac{f(x)-f(0)}{x}\to f'(0)$ so that $\frac{f(x)-f(0)}{x}=O(1)$ as $x\to0$ ).

And if $g(u)=O(u)$ as $u\to0$ , then $g(u)\to_{u\to 0} 0$ , so that we can compose: $f(g(u))=f(0)+O(g(u))=f(0)+O(u)$ . This can be written $f(O(u))=f(0)+O(u)$ as $u$ tends to 0.

Now, in this expansion, you can replace $u$ by any sequence which converges to 0. For instance, $f(O\left(\frac{1}{n^2}\right))=f(0)+O\left(\frac{1}{n^2}\right)$ . If $f=\exp$ , you get what I wrote and used.

(I'm thinking of something that may have been confusing: when I wrote $e\left( 1+O\left(\frac{1}{n^2}\right)\right)$ , it meant $e\times \left( 1+O\left(\frac{1}{n^2}\right)\right)$ , not exponential of the parenthesis)