HELP. Please show your work . Assume you have two algorithms, A and B, both of w

Question

HELP. Please show your work.

Assume you have two algorithms, A and B, both of which perform the same function, although their implementations differ. Assume that algorithm A has a running time of O(N3 + 2N2+6N +10) and algorithm B has a running time of O(6N2 + 3N +10 ). Also assume that the value of N is restricted to the set of Natural numbers i.e., {1, 2, 3, ...}. Answer the follow­ing questions:

For what values of N Algorithm A is more efficient than algorithm B?

For what values of N Algorithm B is more efficient than algorithm A?

For what values of N might both algorithms be expected to operate with the same efciency?

Explanation / Answer

Let us look at the algorithms in more detail:

when N=1

O(N3 + 2N2 +6N +10) = 1+2+6+10=19

O(6N2 + 3N +10 ) = 6+3+10=19

so both are equal and will operate with same efficiency when n=1

n=2

O(N3 + 2N2 +6N +10) = 8+8+12+10=38

O(6N2 + 3N +10 ) = 24+6+10=40

Now in this case algorithm A is efficient then algorithm B

n=3

O(N3 + 2N2 +6N +10) = 27+18+18+10=73

O(6N2 + 3N +10 ) = 54+9+10=73

Both the algorithms will be same and will operate with same efficiency in this case

n=4

O(N3 + 2N2 +6N +10) = 64+32+24+10=130

O(6N2 + 3N +10 ) = 96+12+10=118

Now algorithm B will be more efficient.

Since this A has N3 in the equation it will be worse thatn algorithm B.

N=2 Algorithm A is more efficient

N>=4 Algorithm B is more efficient

N=1,3 Same efficiency.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.