Chapter 2

Question 1

Define Efficiency

Answer 1

An algorithm is efficient if it has a polynomial running time.

Question 2

Define Polynomial Time

Answer 2

a polynomial-time algorithm is one whose running time T(n) is O(n^d) for some constant d, where d is independent of the input size.

Question 3

What is the asymptotic upper bound for a polynomial?

Answer 3

Let f be a polynomial of degree d, in which the coefficient ad is positive. Then f = O(n^d).

Question 4

What is the asymptotic upper bound for a logarithm?

Answer 4

For every b>1 and every x>0, we have logb n=O(n^x).

Question 5

What is the asymptotic upper bound for an exponent?

Answer 5

For every r>1 and every d>0, we have n^d=O(r^n).

Question 6

What is a common trait among linear time algorithms?

Answer 6

They can be linear time because they spend a constant time on each input received or for subtler reasons (see explanation of merging 2 sorted lists in textbook)

Question 7

What is a common trait among O(n log n) time algorithms?

Answer 7

it is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time.(i.e MergeSort)

Can also be encountered when the most expensive step of an algorithm is to sort input.

Question 8

What is a common trait among O( n^2) time algorithms?

Answer 8

Looping through 2 loops

Question 9

What is a common trait among O(log n) time algorithms?

Answer 9

O(log n) arises as a time bound whenever we’re dealing with an algorithm that does a constant amount of work in order to throw away a constant fraction of the input.