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
I have a homework problem and it goes like this:

"Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?

(Goes on to list problems)"

Is T1 the same as f as used in this context? Are both functions?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
I have a homework problem and it goes like this:

"Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?

(Goes on to list problems)"

Is T1 the same as f as used in this context? Are both functions?
Clearly they are both functions, and clearly they are not necessarily the same function.

Why? Because "__ = O(__)" relates two functions to one another.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
So is it correct to say that we know that T1(N), f(N), and T2(N) could all equal anything? Is it correct to also say we also know that whatever T1(N) is it is less than or equal to f(N) and that whatever T2(N) is it is also less than or equal to f(N)?
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
So is it correct to say that we know that T1(N), f(N), and T2(N) could all equal anything? Is it correct to also say we also know that whatever T1(N) is it is less than or equal to f(N) and that whatever T2(N) is it is also less than or equal to f(N)?
I'm not sure what "could all equal anything" means. But it's true that we don't know any of their values.

Do you know what T1(N) = O(f(N)) means? It's not a fact about any particular N, but about the functions as a whole; it doesn't imply that T1(N) ≤ f(N), either for all N, or for some particular N.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
So is it correct to say that we know that T1(N), f(N), and T2(N) could all equal anything? Is it correct to also say we also know that whatever T1(N) is it is less than or equal to f(N) and that whatever T2(N) is it is also less than or equal to f(N)?
Why would you suppose that \(\displaystyle T_1(n) \le f(n)\)?

Also is it \(\displaystyle T_1(n) = O(f(n)) \text { and } T_2(n) = f(O(n))\)?

You said

\(\displaystyle T_1(n) = O(f(n)) \text { and } T_2(n) = O(f(n)).\)

But that means \(\displaystyle T_1(n) = T_2(n).\)

It would help to see the follow up questions and your answers. As it is we have very little context to give you help.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
@JeffM-

The follow-up questions:

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))
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
@JeffM-

The follow-up questions:

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))
Those are more or less the kinds of questions I expected.

The main idea is that there are three different functions, T1, T2, and f, which are related as indicated in terms of "Big-O". ("O" is not a function.) You are to determine how various combinations of them are related. I think that answers your initial questions.

If you want help actually solving this, we'll need to know what you have learned about "Big-O" and "Little-o", and whether you are expected to figure these out from the definitions, or were given some properties you can use. The more you tell us about what you have learned and what you have tried, the better the chance we can help you solve the problem.

So, what were you taught that it means to say "T1(N) = O(f(N))"?
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
@Dr.Peterson-

What I meant by "could equal anything" is that any of the functions could equal any value. f(N), for instance, could equal 5, x + 2, x2 + x + 2, ect..

But I thought that T1(N) = O(f(N)) basically means that T1(N) will never exceed the growth rate of f(N) which is the same as T1(N) <= f(N) for all N. What would it mean otherwise?

@JeffM-

I did mean what I wrote. But how would that mean that T1(N) = T2(N)? How would I know that both are the same? All the initial statement would suggest is that both individually have a lower growth rate than f(N), right?
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
@Dr. Peterson-

Yeah. I learned that big-Oh is a way of comparing the growth rates of different functions.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
@Dr.Peterson-

What I meant by "could equal anything" is that any of the functions could equal any value. f(N), for instance, could equal 5, x + 2, x2 + x + 2, ect..

But I thought that T1(N) = O(f(N)) basically means that T1(N) will never exceed the growth rate of f(N) which is the same as T1(N) <= f(N) for all N. What would it mean otherwise?

@JeffM-

I did mean what I wrote. But how would that mean that T1(N) = T2(N)? How would I know that both are the same? All the initial statement would suggest is that both individually have a lower growth rate than f(N), right?
Well, f might be any function; but what you are told will restrict what the other functions might be. But it sounds like what you were thinking (as opposed to what you said) was basically right.

I'm guessing that JeffM misread O as being a function, because it doesn't imply that T1(N) = T2(N).

You are aware that having a slower growth rate is different from actually being less, right? That's why we have this notation, and don't just say T1(N) <= f(N). You might have T1(N) starting out greater than f(N), but eventually being less.

Now, we still need to know what you know about O, and what sort of work you can do to answer the questions. The definition is more detailed than "lower growth rate".
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
@Dr.Peterson-

That is what I know about big-Oh. That it symbolizes the growth relationship between two functions. It indicates that whichever one is big-Oh that at some point its growth rate will always be larger. Ex. T(N) = O(f(N)) means that at some value of N, f(N) will eventually continue to be larger than T(N) forever more.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
Well, for big-Oh the growth rates might eventually be identical. In the case of little-Oh, the function on the right side of the equation (ex. T(N) = o(N)) will eventually be larger and not the same forever more.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
Well, for big-Oh the growth rates might eventually be identical. In the case of little-Oh, the function on the right side of the equation (ex. T(N) = o(N)) will eventually be larger and not the same forever more.
Okay. Those are informal description, not definitions, so you can't prove anything with them; but you can figure out what happens generally.

What answers do you have for the questions? Can you explain in words why, say, you can conclude that this is big-O of that, or that this is not necessarily big-O of that? For the latter, you might use counterexamples; for the former, you have to be careful not to assume too much or miss possibilities.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I don't know how you could know the answer to (a). Depending on the growth rate of T1(N) and T2(N), both combined could eventually have a higher growth rate than f(N) but both combined could also both still have a slower growth rate than f(N). It is impossible to know if it is true or false in the case of (a), right?

For (b) you could safely say that is true. We know that both T1(N) and T2(N) both individually have a faster or equal growth rate to f(N) so one being minused the other would have to have a faster growth rate.

For (c), it is also impossible to know? We don't know what T1(N) and T2(N) are so one being divided by the other means an indeterminate growth rate. So it would be impossible to know here, too, right?

For (d), we also don't know, right? We don't know the value of either T1(N) or T2(N). We only know that both have an equal or faster growth rate than f(N). Depending on the value of either, T1(N) might have a faster growth rate than T2(N) or it might be slower.

I am assuming that all of the problems must have a true or false answer so I must be missing something. But this is how I understand how this works currently.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
I don't know how you could know the answer to (a). Depending on the growth rate of T1(N) and T2(N), both combined could eventually have a higher growth rate than f(N) but both combined could also both still have a slower growth rate than f(N). It is impossible to know if it is true or false in the case of (a), right?

For (b) you could safely say that is true. We know that both T1(N) and T2(N) both individually have a faster or equal growth rate to f(N) so one being minused the other would have to have a faster growth rate.

For (c), it is also impossible to know? We don't know what T1(N) and T2(N) are so one being divided by the other means an indeterminate growth rate. So it would be impossible to know here, too, right?

For (d), we also don't know, right? We don't know the value of either T1(N) or T2(N). We only know that both have an equal or faster growth rate than f(N). Depending on the value of either, T1(N) might have a faster growth rate than T2(N) or it might be slower.

I am assuming that all of the problems must have a true or false answer so I must be missing something. But this is how I understand how this works currently.
There's a lot here that you have to be more careful about. I'm not even sure whether you are confusing faster and slower growth rates. But you also need a clear idea of what a faster growth rate means. Have you been given a definition of that? It's more subtle than you seem to be assuming.

But a central thing you need to be aware of is that when we ask "which of the following are true?", we mean "which are necessarily true?" That is, we are not expecting the conclusion to be true or false, but rather to be always true, or sometimes false. This is why a single counterexample is enough to say no. If you "can't know" that it's true, then you have to ask, can it ever be false? If so, you say no, not "we can't know".

So, for the cases where you are saying we don't know, try thinking of some simple examples (e.g. T1(N) = N, T2(N) = N2, or whatever) that will make the conclusion false.

By the way, you showed (c) as a subtraction, but now you are calling it division. Why?
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
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."
 
Last edited:

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
3,258
@JeffM-

I did mean what I wrote. But how would that mean that T1(N) = T2(N)? How would I know that both are the same? All the initial statement would suggest is that both individually have a lower growth rate than f(N), right?
I did not know that your O stood for big-O notation. It is not a topic normally encountered in Intermediate Algebra, and your previous questions were about logarithms. Jumping to O notation from basic manipulation of logarithms is not an obvious progression.

This why it is so helpful to have students say what they are studying, etc. Otherwise, time gets wasted on irrelevant questions and answers.

Now that I understand how O is being used, you are completely correct that the conclusion I reached was nonsensical. Sorry for that.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
I also apologize @JeffM. I thought that Big-Oh would be a commonly understood topic in this forum but I was incorrect. To be clearer, I am studying computer science runtime algorithms that use Big-Oh notation to compare their relative growth rates.
 

vaderboi

New member
Joined
Jan 18, 2019
Messages
47
Here is what I now think the answers are for each question and my reasoning. Is my reasoning sound? I just need my reasoning to be informally sound. The question doesn't specify me needing to write a formal proof.

a. False, because there exists at least one example of this not being true. Say T1(N) = N2, T2(N) = N3, and f(N) = N3. In this case, if T1(N) and T2(N) were added together, the growth rate would be higher than that of f(N) because N2 + N3 has a higher rate of growth than N3.

b. True, because there exists no value that any of the functions could have that would cause this statement to be false. We know that f(N) must be at least equal to the larger of the two functions since the original declarations say that both T1(N) and T2(N) both have a growth rate that is less than or equal to f(N). For example: if T1(N) = N2, T2(N) = N3 then we know that f(N) must have a faster growth rate than the larger of the two values- N3. Therefore, no matter the value of T1(N) or T2(N), T2(N) being subtracted from T1(N) would either result in a negative or positive value that has a slower growth rate than f(N) because both values are going to be less than f(N).

c. False, because there exists at least one example of this not being true. Say T1(N) = N3, T2(N) = N2, and f(N) = N3. N3 / N2 = N which has a greater rate of growth than 1. Therefore, this statement is false.

d. False, because there exists at least one example of this not being true. Say T1(N) = N3, T2(N) = N2, and f(N) = N3. N3 has a greater rate of growth than N2. Therefore, this statement is false.
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
3,313
Here is what I now think the answers are for each question and my reasoning. Is my reasoning sound? I just need my reasoning to be informally sound. The question doesn't specify me needing to write a formal proof.

a. False, because there exists at least one example of this not being true. Say T1(N) = N2, T2(N) = N3, and f(N) = N3. In this case, if T1(N) and T2(N) were added together, the growth rate would be higher than that of f(N) because N2 + N3 has a higher rate of growth than N3.

b. True, because there exists no value that any of the functions could have that would cause this statement to be false. We know that f(N) must be at least equal to the larger of the two functions since the original declarations say that both T1(N) and T2(N) both have a growth rate that is less than or equal to f(N). For example: if T1(N) = N2, T2(N) = N3 then we know that f(N) must have a faster growth rate than the larger of the two values- N3. Therefore, no matter the value of T1(N) or T2(N), T2(N) being subtracted from T1(N) would either result in a negative or positive value that has a slower growth rate than f(N) because both values are going to be less than f(N).

c. False, because there exists at least one example of this not being true. Say T1(N) = N3, T2(N) = N2, and f(N) = N3. N3 / N2 = N which has a greater rate of growth than 1. Therefore, this statement is false.

d. False, because there exists at least one example of this not being true. Say T1(N) = N3, T2(N) = N2, and f(N) = N3. N3 has a greater rate of growth than N2. Therefore, this statement is false.
Here are the questions as you stated them:

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))
(a) You are wrong here, because you are not thinking about the proper meaning of growth rate. Again, have you been given a definition for this concept? It is not true that N2 + N3 has a higher rate of growth than N3.

(b) How about T1(N) = 2N2, T2(N) = N2? Remember this is little-o, not big-O (unless you mistyped), so even your example is wrong.

(c) I asked before, but you didn't acknowledge that you typed the question incorrectly. Clearly you meant "T1(N) / T2(N) = O(1)". But you are correct about the answer.

(d) You're right.
 
Top