1
$\begingroup$

I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python)

def find(a, target):
    x = 0
    y = len(a)
    while x < y:
        m = (x+y)/2
        if a[m] < target:
            x = m+1
        elif a[m] > target: 
            y = m
        else:
            return m
    return -1

I know that the running time of this code in the worst case is $O(\lg n)$. But the question I was given if the fifth line was changed from $m = \frac{x+y}{2}$ to $m=\frac{2x+y}{3}$, would the running time change?

My intuition is that the running time gets a little larger as it is no longer cutting the list in half like binary search should do which is less efficient, but I am not sure how to calculate what the asymptotic runtime would be at this point.

$\endgroup$
  • 1
    $\begingroup$ How did you get to $O(\lg n)$ in the first place? Adapt your derivation to the new formula and you get your result. (By the way, similar questions have been solved in detail several times before, see algorithm-analysis.) $\endgroup$ – Raphael Sep 10 '13 at 16:48
  • $\begingroup$ I guess it is $\frac{2(x+y)}{3}$? $\endgroup$ – A.Schulz Sep 10 '13 at 17:20
  • $\begingroup$ @A.Schulz, I would guess not. $(2x+y)/3$ is a weighted average of $x$ and $y$ that puts twice the weight on $x$ (i.e., it is between $x$ and $y$, but closer to $x$ than to $y$). $\endgroup$ – D.W. Sep 10 '13 at 19:02
2
$\begingroup$

Instead of cutting the interval in half, it's cut in to a piece 1/3 of the length and it's cut in to a piece 2/3 of the length. If you are lucky enough that the item you're searching for is in the left half, then you've done a better job than regular binary search. If you're unlucky and it ends up in the right half, then you do slightly worse than regular binary search.

What happens if the algorithm has "bad luck" twice in a row. The interval gets cut to 2/3rds and then to 2/3rds again, meaning it gets cut to 4/9ths which means it is now slightly shorter than 1/2. This means that in the worst case (bad luck every time) this version of binary search will take only 2x more steps than regular binary search.

On the other hand, if the algorithm is lucky the interval is cut to 1/3rd. If we look at regular binary search, after two steps the algorithm has been cut in half two times, meaning it has been cut to 1/4th - slightly shorter than a 1/3rd. So in the best case, the algorithm takes at least half as many steps as regular binary search.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.