109k views
1 vote
Suppose that you have two different algorithms for solving a problem. to solve a problem of size n, the first algorithm uses exactly n(log(n)) operations and the second algorithm uses exactly n3=2 operations. as n grows, which algorithm uses fewer operations? justify your answer using definitional proof.

User Elimariaaa
by
8.0k points

1 Answer

4 votes
So we have two expressions n(log(n)) and 3n = 2. The second expression involves less operation. From the second expression we have n = 2/3. If the RHS and LHS will be balanced, then the value of n cannot exceed 2/3. Sowe have no operation at that point. On the other hand when n = 10 we have 10(log(10)) = 1. When n is increased to 100. We have 100(log(100)) = 200 and when n = 300 we have 300(log(300)) = 300 *2.47 = 743.1 As n increase, the logarithmic function also increases, there's no end in sight; on the other hand as n increase in the first operation, once it reaches 2/3, it stops. So the second has fewer operations.
User RealPro
by
8.3k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories