- Thread starter vaderboi
- Start date

- Joined
- Nov 12, 2017

- Messages
- 5,624

Clearly they are both functions, and clearly they are notI have a homework problem and it goes like this:

"SupposeT_{1}(N) =O(f(N)) andT_{2}(N) =O(f(N)). Which of the following are true?

(Goes on to list problems)"

IsT_{1 }the same asfas used in this context? Are both functions?

Why? Because "__ = O(__)" relates

- Joined
- Nov 12, 2017

- Messages
- 5,624

I'm not sure what "could all equal anything" means. But it's true that we don't know any of their values._{1}(N), f(N), and T_{2}(N) could all equal anything? Is it correct to also say we also know that whatever T_{1}(N) is it is less than or equal to f(N) and that whatever T_{2}(N) is it is also less than or equal to f(N)?

Do you know what T

Why would you suppose that \(\displaystyle T_1(n) \le f(n)\)?_{1}(N), f(N), and T_{2}(N) could all equal anything? Is it correct to also say we also know that whatever T_{1}(N) is it is less than or equal to f(N) and that whatever T_{2}(N) is it is also less than or equal to 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.

- Joined
- Nov 12, 2017

- Messages
- 5,624

Those are more or less the kinds of questions I expected.@JeffM-

The follow-up questions:

a. T_{1}(N) + T_{2}(N) = O(f(N))

b. T_{1}(N) - T_{2}(N) = o(f(N))

c. T_{1}(N) - T_{2}(N) = O(1)

d. T_{1}(N) = O(T_{2}(N))

The main idea is that there are

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

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, x

But I thought that T

@JeffM-

I did mean what I wrote. But how would that mean that T

- Joined
- Nov 12, 2017

- Messages
- 5,624

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.

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, x^{2 }+ x + 2, ect..

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

@JeffM-

I did mean what I wrote. But how would that mean that T_{1}(N) = T_{2}(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'm guessing that JeffM misread O as being a function, because it

You are aware that having a slower

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".

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.

- Joined
- Nov 12, 2017

- Messages
- 5,624

Okay. Those are informal description, not definitions, so you can'tWell, 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.

What answers do you have for the questions? Can you explain in words why, say, you can conclude that

For (b) you could safely say that is true. We know that both T

For (c), it is also impossible to know? We don't know what T

For (d), we also don't know, right? We don't know the value of either T

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.

- Joined
- Nov 12, 2017

- Messages
- 5,624

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_{1}(N) and T_{2}(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 T_{1}(N) and T_{2}(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 T_{1}(N) and T_{2}(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 T_{1}(N) or T_{2}(N). We only know that both have an equal or faster growth rate than f(N). Depending on the value of either, T_{1}(N) might have a faster growth rate than T_{2}(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.

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

So, for the cases where you are saying we don't know, try thinking of some simple examples (e.g. T

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

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) = y^{2}. 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 N^{2 }for small values of N, N^{2 }grows at a faster rate, and thus N^{2} will eventually be the larger function."

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

This is the example my textbook,

"Although 1,000N is larger than N

Last edited:

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.@JeffM-

I did mean what I wrote. But how would that mean that T_{1}(N) = T_{2}(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?

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.

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 T_{1}(N) = N^{2}, T_{2}(N) = N^{3, }and f(N) = N^{3}. In this case, if T_{1}(N) and T_{2}(N) were added together, the growth rate would be higher than that of f(N) because N^{2 }+ N^{3 }has a higher rate of growth than N^{3}.

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 Ta. False, because there exists at least one example of this not being true. Say T

c. False, because there exists at least one example of this not being true. Say T

d. False, because there exists at least one example of this not being true. Say T

- Joined
- Nov 12, 2017

- Messages
- 5,624

Here are the questions as you stated them: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.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 T

a. False, because there exists at least one example of this not being true. Say T_{1}(N) = N^{2}, T_{2}(N) = N^{3, }and f(N) = N^{3}. In this case, if T_{1}(N) and T_{2}(N) were added together, the growth rate would be higher than that of f(N) because N^{2 }+ N^{3 }has a higher rate of growth than N^{3}.

_{1}(N) and T_{2}(N) both have a growth rate that is less than or equal to f(N). For example: if T_{1}(N) = N^{2}, T_{2}(N) = N^{3}then we know that f(N) must have a faster growth rate than the larger of the two values- N^{3}. Therefore, no matter the value of T_{1}(N) or T_{2}(N), T_{2}(N) being subtracted from T_{1}(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 T_{1}(N) = N^{3}, T_{2}(N) = N^{2, }and f(N) = N^{3}. N^{3 }/ N^{2 }= 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 T_{1}(N) = N^{3}, T_{2}(N) = N^{2, }and f(N) = N^{3}. N^{3 }has a greater rate of growth than N^{2}. Therefore, this statement is false.

(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 isa. T_{1}(N) + T_{2}(N) = O(f(N))

b. T_{1}(N) - T_{2}(N) = o(f(N))

c. T_{1}(N) - T_{2}(N) = O(1)

d. T_{1}(N) = O(T_{2}(N))

(b) How about T

(c) I asked before, but you didn't acknowledge that you typed the question incorrectly. Clearly you meant "T

(d) You're right.