Give a formula for the total number of operations done by a Sequential Search al

Question

Give a formula for the total number of operations done by a Sequential Search algorithm in the worst case for an array of n entities.

Count comparisons of K with array entries, comparisons with variable index, additions, and assignments to index.

Explanation / Answer

Dear... In our analysis of searching algorithms, both the worst and average time is O(n). it can dropped in the base of the logarithm because from the Change of Base Theorem. For any b > 1, log = ·logb n K n, where log n is logarithm to the base 10, and K = 1/ logb is a positive constant. Since functions that differ only by a positive constant factor have the same order of growth, O(log 2 n) is the same as O(log n). Therefore, when we talk about logarithmic growth, the base of the logarithm is not important, and we say simply O(log n). Worst-Case Analysis: Let W(n) be a function. W(n) is the maximum number of basic operations performed by the algorithm on any input size n. For our example, clearly W(n) = n. The worst cases occur when K appears only in the last position in the array and when K is not in the array at all. Algorithm: int seqSearch(int[] E, int n, int K) int ans, index; ans = -1; // Assume failure. for (index = 0; index

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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