Given an array A[1..n] and a key x, n = 3^k>= 1. If Pr(xeA) = 3 8 and, if x is i

Question

Given an array A[1..n] and a key x, n = 3^k>= 1. If Pr(xeA) = 3 8 and, if x is in A, the probability that x is in the first third of the array is three times more likely for x to be in the second third of the array, and the probability that x is in the second third of the array is twice more likely for x to be in the last third of the array. Furthermore, if x is in any third part of the array, x is equally likely to be found in any one of the positions in that part of the array. Based on the number of comparisons, compute Ta(n) if sequential search is performed on A for x. You must set up the equation for Ta(n) and then evaluate the sums. Do not simplify your expression.

Explanation / Answer

T(n)=3/8(6/9*(n/3)+2/9*(n/3)+1/9*(n/3))+5/8*n

=3/4*n

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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