Difference between T1(N) and f(N): "Suppose T_1(N) = O(f(N)) and T_2(N) = O(f(N)). Is T_1 the same as f in this context?"

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
The closest the book comes to defining growth rates is the following on page 70:

"The idea of these definitions is to establish a relative order among functions. Given two functions, there are usually points where on function is smaller than the other. So it does not make sense to claim, for instance, f(N) < g(N). Thus we compare their relative rates of growth. When we apply this to the analysis of algorithms, we shall see why this is the important measure."

a) How does N2 + N3 not have a higher rate of growth than N3? For every value N, N2 + N3 will result in a higher value than N3. Is it because N2 would become functionally irrelevant for really high values of N?

b) I apologize. I kept forgetting it was little o. But wouldn't my example still be correct? Wouldn't N3 - N2 have a slower growth rate than whatever f(N) is? Based on the original premises, we know that f(N) has to be at least equal to the larger of the two T(N) values. Due to that, T1(N) - T2(N) must either be a positive or negative value that is less than f(N).
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
Somehow, I never saw post #16:

My apologies. For (3), I meant divided.

I will examine the equations as you have just said and then post my reasoning. Yeah. I didn't know how absolute the true or false statements had to be so thank you for clarifying that.

Take f(x) = y and f(x) = y2. The algorithm with the faster growth rate would be the second equation because for every value of x, y is bigger in the second equation than it is in the first equation. Of course, as you pointed out earlier, when comparing two equations to figure out which has the faster growth rate- you have to determine which equation will eventually be larger than the other at a certain value of x. In this case also, we can safely say that the second equation will be larger for every value of x > 1.

This is the example my textbook, Data Structures and Algorithms in C++: Fourth Edition by Mark Allen Weiss, gives about growth rates on page 70:

"Although 1,000N is larger than N2 for small values of N, N2 grows at a faster rate, and thus N2 will eventually be the larger function."
Not only the mention of division, but the references to your textbook, which I didn't think you'd mentioned yet. There must have been too many similar posts at once for me to see clearly.

I did acknowledge it. Look at my comment far up on page 2. I said "My apologies. For (3), I meant divided".

The closest the book comes to defining growth rates is the following on page 70:

"The idea of these definitions is to establish a relative order among functions. Given two functions, there are usually points where on function is smaller than the other. So it does not make sense to claim, for instance, f(N) < g(N). Thus we compare their relative rates of growth. When we apply this to the analysis of algorithms, we shall see why this is the important measure."

a) How does N2 + N3 not have a higher rate of growth than N3? For every value N, N2 + N3 will result in a higher value than N3. Is it because N2 would become functionally irrelevant for really high values of N?

b) I apologize. I kept forgetting it was little o. But wouldn't my example still be correct? Wouldn't N3 - N2 have a slower growth rate than whatever f(N) is? Based on the original premises, we know that f(N) has to be at least equal to the larger of the two T(N) values. Due to that, T1(N) - T2(N) must either be a positive or negative value that is less than f(N).
(a) We would say that N2 + N3 has the same rate of growth as N3. Your textbook is not giving the math as much attention as it needs in order to be clearly understood. As I've said, this can be a lot more subtle than it seems at first, and I imagine a lot of programmers have only a superficial understanding.

Here is the formal definition: https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition . What you are missing is the mention of the constant M: we say that f(x) = O(g(x)) when eventually |f(x)| becomes and remains less than or equal to Mg(x).

In your example, N2 + N3 remains less than 2N3, which means that it does not grow faster, even though it is always greater. Informally, it stays in the same vicinity, not zooming past.

(b) Do you see the issue here now? Look again at my suggestion to consider T1(N) = 2N2, T2(N) = N2, keeping in mind that little-o requires that the difference grow distinctly slower than (as opposed to no faster than) f.

I spent some time looking for a good informal explanation of the concepts, and they are very hard to find. Here is one that does proofs, which you don't need, but that may help: https://www.cs.sfu.ca/~ggbaker/zju/math/growth.html .
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
The closest the book comes to defining growth rates is the following on page 70:

"The idea of these definitions is to establish a relative order among functions. Given two functions, there are usually points where on function is smaller than the other. So it does not make sense to claim, for instance, f(N) < g(N). Thus we compare their relative rates of growth. When we apply this to the analysis of algorithms, we shall see why this is the important measure."

a) How does N2 + N3 not have a higher rate of growth than N3? For every value N, N2 + N3 will result in a higher value than N3. Is it because N2 would become functionally irrelevant for really high values of N?

b) I apologize. I kept forgetting it was little o. But wouldn't my example still be correct? Wouldn't N3 - N2 have a slower growth rate than whatever f(N) is? Based on the original premises, we know that f(N) has to be at least equal to the larger of the two T(N) values. Due to that, T1(N) - T2(N) must either be a positive or negative value that is less than f(N).
A formal definition of O suitable for analysis of algorithms can be found here

http://web.mit.edu/16.070/www/lecture/big_o.pdf

I really think that using the formal definition eliminates confusion that is engendered by "simple" explanations.

\(\displaystyle f(x) = O(g(x)) \text { for } x \rightarrow \infty \iff \exists \ c \text { and } n \text { such that } f(x) \le c * g(x) \text { if } x > n.\)

Let's take your example.

\(\displaystyle f(x) = x^2 + x^3 \text { and } g(x) = x^3 \implies f'(x) = 2x + 3x^2 \text { and } g'(x) = 3x^2.\)

So you are absolutely right that for all positive x f(x) > g(x) and f'(x) > g'(x).[/tex]

But this is not what big O notation tells you. It does not tell you that f(x) is less than x^3 or grows more slowly than x^3.

Consider h(x) = c * g(x) = cx^3 \text { and } c > 1.[/tex]

\(\displaystyle h(x) > f(x) \text { if } x > \dfrac{1}{c - 1} \implies c * g(x) \ge f(x) \text { if } x > \dfrac{1}{c - 1} \implies f(x) = O(g(x)).\)

What O tells you is that, once x is big enough, f(x) is overshadowed by an infinite number of cubics. It is a junior member of a big family.

You may say that is intuitively obvious in this example. Perhaps, but this is a simple case. And getting an exact definition of intuitive feelings avoids lots of errors in even seemingly simple cases. And not all cases are simple.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
@Dr.Peterson and JeffM- I apologize but I still don't understand. N2 + N3 for any input over 1 will always be higher than N3. How does N2 + N3 have the same growth rate as N3? I apologize if I am not understanding what you are saying. I have tried to read over both of the links but they are honestly over my head.

In the web.mit.edu link the first page says this:

"f(x) <= C*g(x) for all x>N. Intuitively, this means that f does not grow faster than g."

Maybe I am misunderstanding this, but to me that would indicate that the value on the left side does not grow faster than the value on the right. But wouldn't N2 + N3 grow faster than N3 ?
 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
@Dr.Peterson and JeffM- I apologize but I still don't understand. N2 + N3 for any input over 1 will always be higher than N3. How does N2 + N3 have the same growth rate as N3? I apologize if I am not understanding what you are saying. I have tried to read over both of the links but they are honestly over my head.

In the web.mit.edu link the first page says this:

"f(x) <= C*g(x) for all x>N. Intuitively, this means that f does not grow faster than g."

Maybe I am misunderstanding this, but to me that would indicate that the value on the left side does not grow faster than the value on the right. But wouldn't N2 + N3 grow faster than N3 ?
As JeffM pointed out, without the actual definition, you don't get a correct idea of what O means. The definition states what we mean by "grows faster", which is not what you are thinking it means. To put it another way, the phrase "grows faster" is a shorthand for what the definition is saying, and is intended only to remind you of that definition, not to express it clearly. The definition is not based on the term "grows faster"; that comes second, and you shouldn't base your thinking merely on the English phrase.

The statement that f = O(g) does not merely mean that at some point f(x) is less than g(x), and it does not mean that the slope of f is less than the slope of g. It means that f(x) doesn't get larger than any fixed multiple of g(x).

Don't stop at the line you quoted. Keep reading, looking at the details, to see what they are talking about. And look also at the page I gave you, which I chose over the MIT page because it gave more examples.

I already answered your specific question here:

In your example, N2 + N3 remains less than 2N3, which means that it does not grow faster, even though it is always greater.
As long as there is some constant (in this case, I used 2) such that f remains less than that multiple of g, we say that f = O(g), and say VERY informally "f does not grow faster than g".

"Growing faster" in this sense means "growing MUCH faster", so that the gap goes beyond merely being proportional; it gets bigger and bigger until you can't even see one function from the other, so to speak.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
@Dr.Peterson and JeffM- I apologize but I still don't understand. N2 + N3 for any input over 1 will always be higher than N3. How does N2 + N3 have the same growth rate as N3? I apologize if I am not understanding what you are saying. I have tried to read over both of the links but they are honestly over my head.

In the web.mit.edu link the first page says this:

"f(x) <= C*g(x) for all x>N. Intuitively, this means that f does not grow faster than g."

Maybe I am misunderstanding this, but to me that would indicate that the value on the left side does not grow faster than the value on the right. But wouldn't N2 + N3 grow faster than N3 ?
Yes, it does say that. I strongly reiterate my suggestion that you dismiss as confusing attempts to explain big O notation in "intuitive" or "simple" terms. Look at what you just quoted. It quite explicitly says formally

\(\displaystyle f(x) \le C * |g(x)|\)

and then IMMEDIATELY says that intuitively means

\(\displaystyle f'(x) \not > g'(x)\),

which is clearly wrong, as I shall now prove using your example.

\(\displaystyle f(x) = x^2 + x^3 \implies f'(x) = 2x + 3x^2.\)

\(\displaystyle g(x) = x^3 \implies g'(x) 3x^2. \)

\(\displaystyle \therefore f(x) - g(x) = x^2 \text { and } f'(x) - g(x) = 2x.\)

\(\displaystyle \therefore f(x) - g(x) > 0 < f'(x) - g'(x) \text { if } x > 0.\)

\(\displaystyle \therefore f(x) > g(x) \text { and } f'(x) > g'(x) \text { if } x > 0.\)

YOU ARE RIGHT.

Now let's talk seriously about Big O notation.

\(\displaystyle 0 < \epsilon < 1.\)

We are thinking about epsilon as a very tiny positive number.

\(\displaystyle \text {Let } n = \dfrac{1}{\epsilon},\ c = (1 + \epsilon), \text { and } h(x) = c * g(x).\)

\(\displaystyle x = p > n \implies f(p) = p^2 + p^3, h(p) = cp^3 = p^3 + p^3 \epsilon,\)

\(\displaystyle f'(p) = 3p^2 + 2p, \text { and } h'(p) = 3cp^2 = 3p^2 + 3p^2 \epsilon. \)

\(\displaystyle f(p) - h(p) = p^2 - p^3 \epsilon = p^2(1 - p \epsilon) = p^2 * \left ( \dfrac{n}{n} - p * \dfrac{1}{n} \right ) = \dfrac{p^2}{n} * (n - p).\)

\(\displaystyle \therefore p > n \implies f(p) - h(p) < 0 \implies f(p) < h(p) \implies f(p) \le h(p).\)

For large enough x, f(x) never exceeds a multiple of g(x).

\(\displaystyle f'(p)= 3p^2 + 2p \text { and } h'(p) = 3p^2(1 + \epsilon ) \implies\)

\(\displaystyle \dfrac{f'(p)}{h'(p)} = \dfrac{3p^2}{3p^2(1 + \epsilon} = \dfrac{1}{1 + \epsilon} < 1.\)

For large enough x, f'(x) never exceeds a multiple of g'(x).

What is even more important, however, is that with small enough epsilon

\(\displaystyle \displaystyle \lim_{x \rightarrow \infty} \dfrac{f'(x)}{g'(x)} = 1.\)

For large enough x, the ratio of f'(x) and g'(x) approaches or equals a positive constant.

Now in your example the multiple and constant happen to be 1. This will not normally be the case.

I am sure there is a good reason (but I do not know it) why the multiple is dropped in informal discussion. But the multiple is key as reference to the formal definition makes obvious.

REVISED EDIT: Dr. Peterson and I have talked. He has suggested that my use of derivatives and \(\displaystyle \delta\)-\(\displaystyle \epsilon\) logic may be introducing concepts that the OP is not familiar with. There is no disagreement between our posts, but they are giving very different perspectives.
 
Last edited:

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I will look over this soon and let you both know any questions I have. Thank you for taking the time to help me with this. This is apparently more advanced than I thought. That's fine but it will take me more time to understand than I was thinking.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
So I talked about the problem with my tutors at the school and I think I understand it a little bit better, but I'm not sure. Can I clarify with you both?

|f(x)|≤C|g(x)| for all x>k.

is the formal definition for big-Oh notation given in the www.cs.fsu.ca link.

For example in problem (a): T1(N) + T2(N) = O(f(N))

it would only take one example of this being wrong for the statement to be wrong, correct?

Say, T1(N) = N2, T2(N) = N3, f(N) = N3, C = -1, x > - 3; I will then try to see if the statement is true if x = -2

| (-2)2 + (-2)3| <= -1 * |(-23)|

|4 + -8| <= -1 *|-8|

|-4| <= -1 * 8

4 <= -8

This example would make the statement untrue so wouldn't that mean that (a) is false? Or is my reasoning still bad?






 
Last edited:

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
So I talked about the problem with my tutors at the school and I think I understand it a little bit better, but I'm not sure. Can I clarify with you both?

|f(x)|≤C|g(x)| for all x>k.

is the formal definition for big-Oh notation given in the www.cs.fsu.ca link.

For example in problem (a): T1(N) + T2(N) = O(f(N))

it would only take one example of this being wrong for the statement to be wrong, correct?

Say, T1(N) = N2, T2(N) = N3, f(N) = N3, C = -1, x > - 3; I will then try to see if the statement is true if x = -2

| (-2)2 + (-2)3| <= -1 * |(-23)|

|4 + -8| <= -1 *|-8|

|-4| <= -1 * 8

4 <= -8

This example would make the statement untrue so wouldn't that mean that (a) is false? Or is my reasoning still bad?
Yes, you've missed key parts of the definition. It says that f = O(g) if there is some value of c for which the inequality is eventually true. To show that f is not O(g), you have to show that there is no such value of C, not that you can pick any values of x and of C to make the inequality false.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
Ah. I also missed that the cs.sfu.ca link explicitly says "...if there are positive constants C and k...". So C and x HAVE to be positive, which makes sense. But why is that there only needs to be at least one example of C in order to make sure that f = O(g)? Wouldn't all the examples of f = O(g) not being true mean that the growth relationship is not true in all cases and therefore false? Why is it that only one example of it being true is sufficient?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
Ah. I also missed that the cs.sfu.ca link explicitly says "...if there are positive constants C and k...". So C and x HAVE to be positive, which makes sense. But why is that there only needs to be at least one example of C in order to make sure that f = O(g)? Wouldn't all the examples of f = O(g) not being true mean that the growth relationship is not true in all cases and therefore false? Why is it that only one example of it being true is sufficient?
Because that's what it means to say " IF THERE ARE positive constants ...". If such a constant exists, then the definition applies. There will, of course, be infinitely many such constants, but you only need to show the existence of one.

I'm not sure how the existence of functions for which f=O(g) is false affects what you have to do to prove that it is in any specific case.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
Say f(x) = O(g(x))

So, for the big-oh relationship to be true there technically only needs to be one instance of C and k that satisfies the big-Oh definition? If that is true, if you could find the lowest values of C and k that satisfy the definition, would that definition constitute the exact value of k at which g(x) begins to surpass f(x) in terms of growth rate?
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I guess what I am trying to ask is, why does only one instance of C and k making a big-Oh definition true enough to satisfy the requirements of a big-Oh definition?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
Say f(x) = O(g(x))

So, for the big-oh relationship to be true there technically only needs to be one instance of C and k that satisfies the big-Oh definition? If that is true, if you could find the lowest values of C and k that satisfy the definition, would that definition constitute the exact value of k at which g(x) begins to surpass f(x) in terms of growth rate?
I guess what I am trying to ask is, why does only one instance of C and k making a big-Oh definition true enough to satisfy the requirements of a big-Oh definition?
Are you asking why the definition is what it is, or why this is how you apply the definition?

As I said, the definition explicitly tells you that

f(x) is O(g(x)) if there are positive constants C and k such that |f(x)| ≤ C|g(x)| for all x > k.[FONT=MathJax_Main][/FONT]

That means that if you can find some value of C and some value of k that make it true, you are done.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I am asking both.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
Okay. I think I am finally starting to understand how to evaluate any given big-Oh definition.

Just to refresh everyone so they don't have to go back to a previous page- here is my homework question in its entirety:

Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?
a. T1(N) + T2(N) = O(f(N))
b. T1(N) - T2(N) = o(f(N))
c. T1(N) / T2(N) = O(1)
d. T1(N) = O(T2(N))


Before I examine b - d, I just want to make sure I understand a. I think a is true and here is my reasoning:

True, because there exists at least one example of this being true. If T1(N) = N2, T2(N) = N3, f(N) = N3, C = 10, and k = 0, then the definition is true. For all values more than 0, N2 + N3 is less than or equal to 10 * N3.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
Okay. I think I am finally starting to understand how to evaluate any given big-Oh definition.

Just to refresh everyone so they don't have to go back to a previous page- here is my homework question in its entirety:

Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?
a. T1(N) + T2(N) = O(f(N))
b. T1(N) - T2(N) = o(f(N))
c. T1(N) / T2(N) = O(1)
d. T1(N) = O(T2(N))


Before I examine b - d, I just want to make sure I understand a. I think a is true and here is my reasoning:

True, because there exists at least one example of this being true. If T1(N) = N2, T2(N) = N3, f(N) = N3, C = 10, and k = 0, then the definition is true. For all values more than 0, N2 + N3 is less than or equal to 10 * N3.
No, one example is not enough.

They are asking whether it is true that T1(N) + T2(N) = O(f(N)). That doesn't mean "T1(N) + T2(N) = O(f(N)) for some functions T1, T2, and f", but "whenever T1(N) = O(f(N)) and T2(N) = O(f(N)), it will be true that T1(N) + T2(N) = O(f(N))".

That is, you want to affirm or deny that, "if you know that T1(N) = O(f(N)) and T2(N) = O(f(N)), you can be sure that there exist C and k such that ...".

A single example is enough to show that such a statement is not (always) true.

In the same way, a single example is not enough to prove that all cats are black; but if you find a single white cat, you have proved that it is not true that all cats are black.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
So I have to prove whether the definition is always true for every possible value of every function in the definition?
 
Last edited:

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I apologize for my confusion regarding all of this. I just want to make sure I understand the concepts since I have very little understanding of how to prove definitions in mathematics. I appreciate all of your help and patience.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,331
So I have to prove whether the definition is always true for every possible value of every function in the definition?
Right. The statement you are asked to identify as true or false is about all functions that fit the stated conditions, even though it doesn't use the word "all".

For a parallel question on a more familiar topic, consider this:
Suppose that Pal is a mammal. Which of the following are true?

1. Pal gives milk.
2. Pal has brown hair.
3. Pal has scales.
4. Pal has four legs.
5. Pal breathes.

Some of these are true only of some mammals; giving the example "My dog Pal is a mammal and has brown hair" would not prove (2) true. (You could instead give a counterexample, "Bossie the cow is a mammal and is white", to show that it is false.) Some are true of all mammals, and other animals as well; you could go to the definition of "mammal" to show that any mammal has four legs and breathes. Some are not true of any mammals. Some are subtle; you might initially think that (a) is true, but in fact it is true only of female mammals, so you have to read the definition carefully. These illustrate some of the things that can happen with this sort of question.

I apologize for my confusion regarding all of this. I just want to make sure I understand the concepts since I have very little understanding of how to prove definitions in mathematics. I appreciate all of your help and patience.
Clearly, the problem is that the course you're taking is not (as some courses covering this material would be) a course about proofs; so you have not been taught how to interpret definitions and how to prove statements using them. The trouble, as we've said before, is that this topic really shouldn't be treated as informally as they have done, because it is far more complicated than it appears at first, and informal explanations can be misleading. At the very least, they should have given a lot more examples and explanations than you reported that they did, to give you a clearer picture of what is meant. But some example proofs would be much better.
 
Top