I would appreciate any input anyone might have for the following problem:
Describe the worst-case time complexity, measured in terms of comparisons, of the following searching algorithm:
(x: increasing integer a1, a2, a3.... an)
i=1//left end point
j=n//right end point
while (i<j)
t=[ (i+j/3) ]
begin
if ( x < t )
j=t
else if (x<2*t)
i=t
j=t*2
else
i=t*2
j=j
end
if x= ai then location i
else location = 0
This looks like a variation on binary search. It divides the range a1..an into three equal pieces (roughly) and uses two comparisons to determine in which third x lies. The worst case occurs (I think) if x is not on the list and also if x = a(n-1). The number of points ai in each interval is, after cutting the interval into 3 parts k times, about n/(3^k). I'll leave the rest to you.
thanx for the info...
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.