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

• DorumonSg
In summary, the author is trying to figure out how to solve a Limit problem and they are having trouble understanding it. They mention the Limit of n approching inifinity, the L Hospital Rule, and how to tell when a number is close to inifinity. They also mention that the exponential function grows faster than the normal multiplication function so the whole thing goes towards zero.
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.

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)

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.

Quinzio said:
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.

Inferior89 said:
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?

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.

Inferior89 said:
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?

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.

Inferior89 said:
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?

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.

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.

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.

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?

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.

Last edited:

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?

1. What is the difference between Big-Oh, Big Omega, and Big Theta notation?

Big-Oh, Big Omega, and Big Theta are all notations used in the analysis of algorithms. Big-Oh notation (O) describes the upper bound or worst-case performance of an algorithm. Big Omega notation (Ω) describes the lower bound or best-case performance of an algorithm. Big Theta notation (Θ) describes both the upper and lower bounds of an algorithm, indicating that the algorithm has a consistent performance.

2. How do I determine the time complexity using Big-Oh, Big Omega, and Big Theta notation?

To determine the time complexity of an algorithm using these notations, you need to analyze the algorithm's performance for different input sizes. Then, you can compare the running time with the input size to find the appropriate notation. For example, if an algorithm has a running time of O(n), it means that the algorithm's performance will not exceed n steps for any input size.

3. How can I use Big-Oh, Big Omega, and Big Theta notation to compare algorithms?

Big-Oh, Big Omega, and Big Theta notations allow you to compare the performance of different algorithms. If two algorithms have the same notation, it means they have the same upper or lower bound, making them equally efficient. However, if one algorithm has a better notation than the other, it means that it has a better performance for certain input sizes. Therefore, you can use these notations to determine which algorithm is more efficient for a particular task.

4. Is it possible for an algorithm to have different Big-Oh, Big Omega, and Big Theta notations?

Yes, it is possible for an algorithm to have different notations. This can happen when the algorithm has different performance for different input sizes. For example, an algorithm may have a Big-Oh notation of O(n^2) for the worst-case, a Big Omega notation of Ω(n) for the best-case, and a Big Theta notation of Θ(n^2) for the average-case. Therefore, it is essential to specify the input size and the performance when using these notations.

5. Can I use Big-Oh, Big Omega, and Big Theta notation for space complexity as well?

Yes, Big-Oh, Big Omega, and Big Theta notations can also be used for space complexity. Instead of analyzing the running time of an algorithm, you would analyze the space or memory usage. However, it is essential to specify which complexity (time or space) you are referring to when using these notations to avoid confusion.

• Calculus and Beyond Homework Help
Replies
9
Views
2K
• Calculus and Beyond Homework Help
Replies
6
Views
627
• Calculus and Beyond Homework Help
Replies
1
Views
953
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
13
Views
2K
• Calculus
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
3K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
1K