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.

Improve this question
$\endgroup$
3
  • 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
    Commented Sep 10, 2013 at 16:48
  • $\begingroup$ I guess it is $\frac{2(x+y)}{3}$? $\endgroup$
    – A.Schulz
    Commented Sep 10, 2013 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. ♦
    Commented Sep 10, 2013 at 19:02

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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