1. Give an asymptotically tight bound to each of the following expressions: 3n^2

Question

1. Give an asymptotically tight bound to each of the following expressions:

3n^2 + 2n^3

3n log n + 2n^2

2^n + 3^n

2. Arrange the following asymptotic family from lower order to higher order. The first has been done for you.

O(n log n)

O(n^3)

O(log n)

O(n^2 log n)

O(n)

O(3^n)

O(2^n)

3. At work, Peter needs to solve a problem of different sizes. He has two algorithms available to solve the problem. Algorithm A can solve the problem with size n in time T(n) = n^3 +3n^2+507 milliseconds while Algorithm B can solve the same problem in time T(n)= 100n^2+300n+507 milliseconds. Find the minimum problem size n where Algorithm B runs faster than Algorithm A.

n=

4. True or False:

3n+n^2=O(n)

3n+n^2=O(n^2)

3n+n^2=O(n^3)

Explanation / Answer

1. Give an asymptotically tight bound to each of the following expressions: 3n^2 + 2n^3 => O(n^3) 3n log n + 2n^2 => O(n^2) 2^n + 3^n => O(3^n) 2. Arrange the following asymptotic family from lower order to higher order. The first has been done for you. O(n log n) O(n^3) O(log n) O(n^2 log n) O(n) O(3^n) O(2^n) Answer: --------- O(log n) O(n) O(n log n) O(n^2 log n) O(n^3) O(2^n) O(3^n) 3. At work, Peter needs to solve a problem of different sizes. He has two algorithms available to solve the problem. Algorithm A can solve the problem with size n in time T(n) = n^3 +3n^2+507 milliseconds while Algorithm B can solve the same problem in time T(n)= 100n^2+300n+507 milliseconds. Find the minimum problem size n where Algorithm B runs faster than Algorithm A. n=100 4. True or False: 3n+n^2=O(n) -> False 3n+n^2=O(n^2) -> True 3n+n^2=O(n^3) -> True

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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