Question 1 (40 points) the truth of of the following statements. Cirche (o) the

Question

Question 1 (40 points) the truth of of the following statements. Cirche (o) the number if it is and cross the number 1. The best-case running time of the merge sort algorithm is O(n x lg worst-case running time O(n2), where n is the array size. is and th 2. The quick-sort algorithm is in-place, but the merge-sort algorithm is not in plac 3. The worst-case running time of insertion-sort is o(m2), and the best-case runni time is O(n), where n is the array size 4. alog nlogg n+1 6. For any two functions f(n) and g (m), f(m) S20g n)) if g (m) (n) i el

Explanation / Answer

Answer:

1. False , because the merge sort is the only algorithm which has best , worst and average case O(nlogn) not O(n).

2. True , because we do not require extra space for quick sort but for merge sort , we need extra space like to merge two arrays , we need an extra array to merge two arrays.

3. True, insertion sort has O(n^2) because number of comparisons and swaps.

4. n^log a = a^logn

apply log on both sides , we get

log(n^loga) = log(a^logn)

loga * logn = logn *loga

loga * log n = loga *logn ( so both are equal) , True

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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