Whenever you are designing an algorithm you must address the three questions we

Question

Whenever you are designing an algorithm you must address the three questions we are typically posing (correctness, complexity and improvement potential). The faster your algorithm, the better your mark. Assignment 1 Question 1: Consider the following algorithm // L is a list and n is its length// // For the purpose of this assignment we assume that n= 4**k, for k21// Alg1 (L,n) remove the smallest and largest element from L fn-2> (4"k)/2 call Alg1 (L, n-2) a) What is the algorithm intended to do? b) Is it correct? If it is not correct discover the error(s) when trying to prove c) d) correctness and fix it (them). Then, reprove the correctness. What is its time complexity? Can it be improved? You may use any algorithm discussed in class.

Explanation / Answer

a) algorithm Will call recursively itself up to n-2 is greater than (4**k)/2

b) no, it is not correct, because k value is not defined..

To fix it let k=L

c) Time complexity in worst case is O(n)

d) no, because it is linear decreament

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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