Analysis & Design of Algorithm

page 3 to 4

1. In computer science, linear search or sequential search is a method for finding an element within a list

2. The best case of sequential search is if the first element of the list is the target.

3. The average case time complexity of sequential search, also known as linear search, is O(n), where n is the number of elements in the list or array being searched. This occurs when the element to be searched is in the middle of the array.

4. The worst case time complexity of sequential search, also known as linear search, is O(n),

5. Linear search is a sequential search algorithm that finds a key element in an array by comparing it to each element in order

6. (1) the list we are searching,

   (2) an index to the last element in the list,'

   (3) the target, and

   (4) the address where the found element's index location is to be stored.

7. The Best Case occurs when the target element is the middle element of the array.

8. • Phonebook search: Find a person's name given their phone number

     • Library catalog: Find books by author, title, or genre

     • Dictionary search: Find the definition of a word

     • E-commerce sorting: Filter products by price, brand, or customer reviews

page 9 -10

1. In computer science, a binary search algorithm is a search algorithm that finds the position of a target value in a sorted array.

2. It can only be implemented over a sorted array

3. The recursion relation for the time complexity of a binary search algorithm is T(n) = 2T(n/2) + k, where k is a constant.

4. The time complexity of binary search is O(log n),

5. Divide and conquer, Dynamic programming, Greedy, Backtracking, Brute force, Recursive, Branch and bound

6. Binary search follows the divide and conquer

7. Binary search is more efficient than sequential search, but it is more complex to implement.

8. The time complexity of the binary search algorithm is O(1) in the best case, O(log N) in the average case, and O(log N) in the worst case.

page 13-14

1. The worst-case (and average-case) complexity of the insertion sort algorithm is O(n²). Meaning that, in the worst case, the time taken to sort a list is proportional to the square of the number of elements in the list.

2. The worst-case (and average-case) complexity of the insertion sort algorithm is O(n²).

3. O(n) time complexity

4. Selection sort performs (at most) n – 1 swaps between data elements,

5. Insertion Sort

6. nsertion sort is the sort that results when we perform a PriorityQueueSort implementing the priority queue with a sorted sequence.

page 18-19

1. The time complexity for the Merge Sort algorithm is O(n log n) in all cases,

2. Left half: 25 57 48 37

   Right half: 12 92 86 33

   12 25 33 37 48 57 86 92

3. Left half: 25 57 48 37

   Right half: 12 92 86 33

   12 25 33 37 48 57 86 92

4. Q1: 12 25

   Q2: 33 37

   Q3: 48 57

   Q4: 86 92

   Merge Q1 and Q2: 12 25 33 37

   Merge Q3 and Q4: 48 57 86 92

   Output of 3rd pass: 12 25 33 37 48 57 86 92

5. Merge sort's time complexity is O(n log n) in all cases, including best, average, and worst.

6. It is based on the divide and conquer approach. It divides the complete array into small sub arrays until each sub array contains an element and then sort them and merge them