Questions is from algorithams analysis and design course. 1. (a) Suppose a sorti

Question

Questions is from algorithams analysis and design course.

1.
(a) Suppose a sorting algorithm takes 2 seconds to sort 50 items. How much time in seconds will the same algorithm take to sort 250 items if the number of operations the algorithm performs is exactly n2.

(b) Suppose algorithm A takes 500nlog2 n time and algorithm B takes 4n2 time. What is the smallest value of n (assuming n > 2) for which A will be faster than B? It may be dicult to do an exact calculation here; if so, try to give an approximate answer.

(c) For each of the following, indicate whether the statement is true or false:

i. 3n2 + 6n is O(n3).

ii. 3n4 is O(n2).

iii. n2 is O(log2 n).

iv. 200n2 is O(2n).

v. 3n2 + 9n is O(n2).

(d) If p(n) and q(n) are two functions such that p(n) is O(q(n)), does this always mean that for every value of n, p(n) q(n)? If you think the answer is yes, give a justication. If you think the answer is no, give a counterexample i.e. nd two functions p(n) and q(n) and a number y such that p(n) is O(q(n)) and p(y) > q(y).

2.
(a) Trace insertion sort on the list 7,5,1,4,2,6 i.e. show what the list looks like after each iteration of the outer loop. Also, calculate the exact number of total data comparisons made. Note that a data comparison is when two dierent pieces of data are compared, and not when loop variables etc are compared.

(b) Trace the merge algorithm (not the complete merge sort) on the two lists 1,5,7,14 and 2,4,8,11. Show what the combined list (i.e. the merged list) looks like after every step and also calculate the exact number of total data comparisons made.

Explanation / Answer

since there are 2 questions i am answerig only 1 question as per chegg rules.

Q1)

a)algo is of 0(n^2) complexity si if it takes 2sec for 50 operations, than for 250 operation it will take= (250/50)^2 * 2 =50sec

b)we want 500nlog2 n < 4n2 for smallest n, so

500log2n < 4n

125log2n<n (assuming the log is based 2)

the equations solves for approximately n=15

c)i)True

ii)FALSE

III)false

4)false

5)true

d) No, assume p(n)=5*n so q(n) will be n and for n =1

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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