Need clarification on Limits/Big-Oh/Big Omega/Big Theta

[DorumonSg]

I have a Quiz on this Friday on Big-Oh and stuff, its an algorithm course so we weren't taught anything about Limits and stuff and yet we have to use them...

I tried reading up on Limits abit but I really don't understand a thing or rather I don't have time to go through everything as its not the focus of my course, so I hope someone can answer some basic Limits questions that I need to know for my course.

Firstly, if I have f(n) and f(g), I am going to need to solve "Limit of n approching inifinity f(n)/g(n)" to determine whether its Big-O/Big Omega or Big Theta. How do I solve it? Can I just plug in ANY number? I can't calculate inifinity.

Secondly, after we solve "Limit of n approching inifinity f(n)/g(n)", how do we determine whether its Big-O/Big Omega or Big Theta? What I meant is according to definition :

< inifinity means Big-Oh
> 0 means Big Omega
0 < c < inifinity means Big Theta

Which doesn't any sense to me? All positive number range between these 3 conditions afterall...

Lastly, it says to use the L Hospital Rule if both f(n) and g(n) are really big and close to inifinity... how do I tell whether they are?

I mean I have an example where :

Limit of n approching inifinity 4n + 3/n = 4 < infinity (No L Hospital Rule used)

And

Limit of n approching inifinity 4n / e^n = 0 (L Hospital Rule used)

How is 4n bigger then 4n + 3? I don't understand at all.

 

[Inferior89]

You can use l'Hopital when lim f(x) = lim g(x) = 0 or +- infinity, the derivatives of f(x) and g(x) exist and you want to calculate lim f(x)/g(x). This is then equal to lim f'(x)/g'(x)

 

[Quinzio]

I mean I have an example where :

Limit of n approching inifinity 4n + 3/n = 4 < infinity (No L Hospital Rule used)

Just use commone sense here.

With a calculator compute
(4n+3)/n
for n = 10^20

Every calculator will round up 4*10^20+1 with 4*10^20 and will return 4 to your division.
No wonder that the bigger I choose n, the closer the result will be 4.

That's in practice the limit. The number to which the result will tend.

 

[Inferior89]

Just use commone sense here.

With a calculator compute
(4n+3)/n
for n = 10^20

Every calculator will round up 4*10^20+1 with 4*10^20 and will return 4 to your division.
No wonder that the bigger I choose n, the closer the result will be 4.

That's in practice the limit. The number to which the result will tend.

No need for a caclulator..

(4n+3)/n, when n --> infinity the 3 is insignificant
4n/n = 4.

 

[DorumonSg]

You can use l'Hopital when lim f(x) = lim g(x) = 0 or +- infinity, the derivatives of f(x) and g(x) exist and you want to calculate lim f(x)/g(x). This is then equal to lim f'(x)/g'(x)

Limit of n approching inifinity 4n / e^n = 0 (L Hospital Rule used)

Y is the L Hospital Rule needed here then?

 

[Inferior89]

Because both 4n --> infinity and e^n --> infinity as n --> infinity.

Or you can just know that the exponential function grows faster than the normal multiplication function so the whole thing goes towards zero.

 

[DorumonSg]

Because both 4n --> infinity and e^n --> infinity as n --> infinity.

Or you can just know that the exponential function grows faster than the normal multiplication function so the whole thing goes towards zero.

I know that they are near infinity but I can't tell why?

Like the previous example 4n + 3/n, aren't both f(g) and f(n) near infinity too?

 

[Inferior89]

They are not 'near infinity'. When n --> infinity 4n --> infinity. Right? And when n --> infinity e^n --> infinity.

In the example 4n + 3/n, 4n --> infinity and 3/n --> 0 when n --> infinity.

You can only use l'Hopital when you are dividing a function with another and both the denominator and nominator goes to the same value and this value is 0 or +- infinity.

 

[DorumonSg]

In the example 4n + 3/n, 4n --> infinity and 3/n --> 0 when n --> infinity.

Y is n reaching 0? Isn't n reaching infinity?

 

[Inferior89]

Yes n goes towards infinity but 3/n (3 divided but n) goes towards 0. The bigger n gets the smaller 3 divided with n gets.

For example 3/1000 is close to 0. 3/100000 is closer to zero. When n --> infinity 3/n --> zero.

 

[DorumonSg]

Oops my bad, my bad. What I meant was (4n + 3)/n, not 4n + 3/n.

Is both f(n) and g(n) reaching infinity now? But no L Hospital was used in the example though.

 

[Inferior89]

You could use L'Hopital because both the nominator and the denominator goes towards infinity. Differentiating nominator and denominator of (4n + 3)/n would give you 4 which is the correct limit.

However you could also write that (4n + 3)/n = 4 + 3/n.
Here 3/n --> 0 when n --> infinity so you are left with the 4 which is the limit.

 

[DorumonSg]

Ah I see. Therefore, is it safe to say for simple functions like (4n + 3)/n I can just sub in a few number to determine where the limit is leaning towards and therefore get the limit.


But for really large number like n/(e to the power of n), where its hard or I can't sub in any numbers and it satisfies the usage of L Hospital, I shuld use the L Hospital?

 

[Inferior89]

You could substitute numbers for n/e^(n) for example 100000/(e^(100000)) which your calculator will say is 0. However this is a quite unreliable method.

Let's say you have n^(100000) / e^(0.00001n). The limit n --> infinity will still be 0 but it will take a veeeery long time for it to go to zero. Here you can either say (if you have showed it in class) that the exponential function grows faster than the other function.

Or you can differentiate 100000 times (LOL!). However this isn't as bad as it sounds. After 100000 differentiations the nominator will be 0 and the denominator will be >0 so the limit will be 0.

L'Hopital can also run into a few problems.
For example $$\frac{e^{x^2}}{e^{x}}, \quad x \to \infty$$.
You can differentiate all you want but it won't get any easier.

 

[DorumonSg]

About Big-Oh/Big Omega/Big Theta :

Limit of n approching inifinity f(n)/g(n) = c < inifinity means its Big-Oh
Limit of n approching inifinity f(n)/g(n) = c > 0 means its Big-Omega
Limit of n approching inifinity f(n)/g(n) = 0 < c < inifinity means its Theta

Does that mean that they are only 2 possible values for functions to be in only one bound :

If c is 0 means its Big-Oh only
If c is infinity means its Big-Omega only

And any other values of that is not negative will be Theta

c can't be a negative value in all 3 cases right?