QUESTION

Let F be an algorithm with complexity function f(n), and let G be an algorithm with complexity function g(n). If there exists a positive constant K such that the ratio f(n)/g(n) is less or equal to K for all n greater or equal to 1, then

		the two algorithms are asymptotically equivalent
		the algorithm F is asymptotically no worse than G
		the algorithm F is asymptotically no better than G
		Nothing intelligent can be said about the relative performance of the two algorithms.

QUESTION

One can sort an array a[ ] as follows. Start by observing tat at stage 0, the array segment consisting of the single element a[0] is sorted. Now suppose that at the stage k, the segment a[0..k] is sorted. Take the element a[k+1], and call it X. By moving some of the elements in a[0..k] one place to the right, create a place to put X in so that now a[0..k+1] is sorted. The algorithm that uses this strategy is called

		bubble sort
		insertion sort
		selection sort
		Quicksort

QUESTION

On the average, performing a sequential search on an array of N elements will require

		N comparisons
		N-1 comparisons
		N/2 comparisons
		None of these are correct

QUESTION

An array a[ ] of N elements is being sorted using the insertion sort algorithm. The algorithm is at the last stage, with the segment of the array in positions 0 through N-2 already sorted. How many array elements will a[N-1] have to be compared to, before it can be placed into its proper position?

Just one

Could be any number of elements between 1 and N-1 (inclusive)

Could be any number of elements between 1 and N (inclusive)

N-1

QUESTION 10

Let F be an algorithm with complexity function f(n), and let G be an algorithm with complexity function g(n). If the ratio f(n)/g(n) converges to 2 as n increases to infinity, then

		the two algorithms are equivalent in efficiency and there is no clear winner
		implementations of F will require twice as much time as implementations of G
		we can deduce that F runs in linear time while G runs in quadratic time
		implementations of F will require twice as much space as implementations of G