Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/377541380119470080
edited tags
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Big O Runtime of various versions of binary search

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))$O(\lg n)$. But the question I was given if the fifth line was changed from "m=(x+y)/2"$m = \frac{x+y}{2}$ to "m=(2*x+y)/3"$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 big Othe asymptotic runtime would be at this point.

Big O of various versions of binary search

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=(x+y)/2" to "m=(2*x+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 big O would be at this point

Runtime of various versions of binary search

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.

Source Link

Big O of various versions of binary search

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=(x+y)/2" to "m=(2*x+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 big O would be at this point