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?
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)\)?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)?
@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-
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, 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.
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.
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 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?
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 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).
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.
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.
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))