I think the answers are: n, i = n (comparison); f(n) = n + 2 belongs to Big-Thet

Question

I think the answers are: n, i = n (comparison); f(n) = n + 2 belongs to Big-Theta(n). Just looking for confirmation.

3. Below is an improved version of sequential search where we append the search key to the end of the list. This way, the search for the key will have to be successful, and therefore we can eliminate the end of the list check altogether. Use this algorithm to answer the questions that follow 1: ALGORITHM SequentialSearch2 (A[0..n - 1], K) 2: / Searches for K in A sequentially using K as a sentinel // Input: An array A(0.n - 1 and an element K // Output: The index of the first element in A that matches K 4 or -1 if there is no match while A[i] K do if-i+1 10: end while 12 13 14 15: 16: end ALGORITHM if i n then else end if return -1 return i What is the problem size of this algorithm? What is the basic operation? What would be the number of basic operations performed using worst-case? a. b. c.

Explanation / Answer

Answers are 1) problem size is indeed n. 2) where as basic operation is A[i] != K 3) and yes, in worst case it runs in O(n)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---