Question

Let us say we have two functions that represent the time taken for program execution of two different programs.

T₁(n)=(n⁵+aⁿ) /b
T₂(n)=n³+aⁿ
Which of the following statements is/are true about the two programs? Assume n is the size of input and a,b are constants, with a>1. Select all that apply:
A. The function T₂Will take less time to execute than T₁For same inputs to both functions for large inputs
B. The order of growth of T₁ Is lesser than the order of growth of T₂
C. Both T₁ And T₂Will grow at the same rate asymptotically
D. The function T₁Will take less time to execute than T₂For same inputs to both functions for large inputs
E. The order of growth of T₁Is greater than the order of growth of T₂

Answer 1

For large inputs, function T₂(n) will execute faster than T₁(n) since it lacks the division by constant b, even though both functions are dominated by the exponential term aⁿ and grow at the same rate asymptotically. The order of growth of T₁(n) is greater than T₂(n) due to the division by b.

Step-by-step explanation:

To compare the time complexity of the two functions T₁(n) and T₂(n), we need to look at the asymptotic behavior of each function as the input size n grows large. For T₁(n) = (n⁵ + aⁿ) / b and T₂(n) = n³ + aⁿ, given that a > 1 and b is a constant, the function aⁿ will eventually dominate both T₁(n) and T₂(n) because the exponential function grows faster than any polynomial.

Therefore, both T₁(n) and T₂(n) are dominated by the aⁿ term. However, when we compare T₁(n) and T₂(n) directly in terms of which will take less time, T₂(n) will take less time because it is not being divided by the constant b, as T₁(n) is. Thus, we can conclude that:

• The function T₂(n) will take less time to execute than T₁(n) for large inputs.
• The order of growth of T₁(n) is greater than the order of growth of T₂(n) because of the division by b, even though both are ultimately dominated by the aⁿ term.
• Both T₁(n) and T₂(n) grow at the same rate asymptotically in terms of the dominantly growing term, which is the exponential term, aⁿ.