Worst-Case Runtime

Question

Question

Line 6 runs T(n/2) times in the worst case.

Line 8 runs T(n/2) times in the worst case.

So, T(n/2) + T(n/2) + d (+ d: for the minor constant time operations)

Using master theorem: 0 < 1 so T(n) = O(n) (Answer: A)

How in the world is the answer D?

Answer 1

Firstly refrain from using links as they can go dead. You could have easily typed the code in the image as I have done below

def select_number(A, low, high):
    if low == high:
        return A[low]
    mid = (low+high) // 2
    if A[mid] < A[mid+1]:
        return select_number(A, mid+1, high)  #line 6
    else:
        return select_number(A, low, mid)     #line 8

The user calls select_number(A, 0, len(A)-1). Without using the master theorem we can see that any invocation of select_number will make at most only one recursive call to itself, each time reducing the input space by half. This is similar to a binary search so your expected running time should be in log n.

You are counting the running times of lines 6 and 8 separately whereas they are mutually exclusive: if one runs the other doesn't. So it is not 2T(n/2), just T(n/2), which is what is the solution in D.