Date Turned in: Purpose: To demonstrate your understanding of analyzing algorith

Question

Date Turned in: Purpose: To demonstrate your understanding of analyzing algorithms. Starting with this assignment, only the testing needs to be on empress.csusm.edu A Review Questions 1 pt per question-10ptsYour score is Type your answers here 1) What does W(n) mean? (W? N? W()?) 2) A. What is W(n) of sequential search? I B. When does it happen? 3) What does B(n) mean? (B?, N?, B(N)?) 4) A. What is B(n) of sequential search? B. When does it happen? 5) Why is A(n) difficult to determine for the real world problems? 6) Why don't we care about constants and lesser terms in a time complexity expression? 7) Prove that 3nA2 +4n O(n42) as I did in the notes. 8) Binary search corresponds to the binary decision tree. tree. Sequential search corresponds to a 9) Thus, the fastest ordered list search does W(n)-Theta(???) comparisons. 10) But, the fastest unordered list search does W(n)-Theta(???) comparisons. B) Programming Binary Search 110 pts) No ADT; Just one source code file - Run my solution program first Your score is: Using Notes-3B.doc, implement and test the binary search function. The pseudo code in the file does not take care of the cases where the element is not found. You must fix the code to take care of such cases and return -1. Your main0 will fill an array of 10 slots with integers 1 3579 11 13 15 17 19 It will then ask the user to enter a number to look for. It will then call binarySearch and display the returned result. e.g. "The number was found in position 5

Explanation / Answer

1)W(n) means worst case complexity.

2) A) W(n) of sequencial search is O(n).

W(n) of sequencial search of space complexity is O(1).

B) In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array. When x is not present, the search() functions compares it with all the elements of arr[] one by one. Therefore, the worst case time complexity of linear search would be (n).

3)B(n) is the Best case complexity.

4) A) B(n) of sequencial is O(1).

B) In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be (1)

5 ) The average case analysis is not easy to do in most of the practical cases and it is rarely done. In the average case analysis, we must know (or predict) the mathematical distribution of all possible inputs.

6)When you are characterizing an algorithm's run time, you generally don't know or choose to ignore the system where it will run. The quote merely means that because the system where the program will run will introduce an unknown constant factor in the run time, it's more-or-less pointless to worry about constant factors at all. But this is just when you're analyzing algorithms. Certainly for a specific implementation for a specific system, you are often very concerned about constant factors.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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