CODEWITHSUNDEEP
pythonalgorithmruntimebig-o
Matt Choi
Matt Choi

Reputation: 169

What is the runtime for this particular algorithm?

I am thinking this particular code is (log n)^2 because each findindex function takes logn depth and we are calling it logn times? Can someone confirm this? I hope one of you can think of this as a small quiz and help me with it.

Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

# Ex
# input find 5 in {15,16,19,20,25,1,3,4,5,7,10,14}
# output 8
# runtime(log n)


def findrotation(a, tgt):
    return findindex(a, 0, len(a)-1, tgt, 0)


def findindex(a, low, high, target, index):
    if low>high:
        return -1

    mid = int((high + low) / 2)

    if a[mid] == target:
        index = index + mid
        return index
    else:
        b = a[low:mid]
        result = findindex(b, 0, len(b)-1, target, index)
        if result == -1:
            index = index + mid + 1
            c = a[mid+1:]
            return findindex(c, 0, len(c)-1, target, index)
        else:
            return result

Upvotes: 1

Views: 82

Answers (1)

Kaidul
Kaidul

Reputation: 15875

This algorithm is supposed to be O(logn) but is not from implementation perspectives.

  • In your algorithm, you're not making decision either to go for left subarray or right subarray only, you're trying with both subarray which is O(N).

  • You're doing slicing on array a[low:mid] and a[mid + 1:] which is O(n).

Which makes your overall complexity O(n^2) in worst case.

Assuming there is no duplicates in the array, an ideal implementation in Python 3 of O(logn) binary search looks like this - 

A=[15,16,19,20,25,1,3,4,5,7,10,14]
low = 0
hi = len(A) - 1


def findindex(A, low, hi, target):
    if low > hi:
        return -1
    mid = round((hi + low) / 2.0)
    if A[mid] == target:
        return mid
    if A[mid] >= A[low]:
        if target < A[mid] and target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else : 
            return findindex(A, mid + 1, hi, target)

    if A[mid] < A[low]:
        if target < A[mid] or target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else :
            return findindex(A, mid + 1, hi, target)

    return -1

print(findindex(A, low, hi, 3))

Upvotes: 2

Related Questions