Final answer:
It is true that if f(n) = O(g(n)) and g(n) = O(T(n)), then f(n) = O(T(n)); this is confirmed by using the formal definitions of Big O notation and shows that the compound function f(n) is bound by T(n) in its growth rate.
Step-by-step explanation:
The statement f(n) = O(g(n)) and g(n) = O(T(n)) implies that f(n) = O(T(n)) is true. To prove this formally, consider the formal definition of Big O notation. It states that a function f(n) is O(g(n)) if there are positive constants C and n0 such that for all n ≥ n0, it holds that f(n) ≤ C*g(n). Similarly, g(n) is O(T(n)) if there are positive constants D and n1 such that for all n ≥ n1, g(n) ≤ D*T(n). Combining these two, we have f(n) ≤ C*g(n) ≤ C*D*T(n) for n ≥ max(n0, n1). This shows that f(n) is indeed O(T(n)) because we have found a constant C*D and a n0 that could be either n0 or n1, whichever is larger, thus satisfying the definition of Big O notation for f(n) with respect to T(n).
False. The statement 'f(n) = O(T(n))' cannot be concluded from the given information. The 'O' notation represents an upper bound, and it does not guarantee that the functions are equal. Even though f(n) and g(n) are both upper bounded by T(n), it doesn't imply that f(n) and T(n) are upper bounded by the same function or that they have the same growth rate.For example, let's consider f(n) = n^2, g(n) = n, and T(n) = n^3. Here, f(n) = O(g(n)) and g(n) = O(T(n)), but f(n) is not O(T(n)) since T(n) grows faster than f(n).