Time complexity of finding index equal to array (sorted) value

Question

This kind of recursion is similar to a binary search, but I'm not sure how to exactly solve the recursion using back substitution.

To find the index where it is equal to the array value (in a sorted array), the code would basically look like this:

find(array, low, high) {
    if high < low
         return -1

    mid = (low + high) / 2
    midval = array[mid]

    if midval == mid
        return mid

    int left = find(array, low, min - 1)
    if left >= 0
        return left

    int right = find(array, mid + 1, high)
    return right
}

So the recurrence relation would look like this:

T(1) = b

T(n) = 2T(n/2) + c
     = 4T(n/4) + c(1+2)
     = 8T(n/8) + c(1+2+4)
     = 16(n/16) + c(1+2+4+8)

     = 2^k T(n/2^k) + (2^k - 1)c
     = 2^(logn)T(1) + (2^(logn) - 1)c
     = 2^(logn)(1+c) - c

I know the time complexity is suppose to be like O(logn) or O(nlogn), but I'm not sure how to get there from this using back subtitution.

dreamcrash · Accepted Answer · 2020-11-12 10:56:44Z

With a sorted array finding an element with a naive implementation has at worst O(n). Hence, a better approach would have a worst-case complexity lower than O(n), so it cannot be O(n logn).

In a typically binary search, one takes advantage of the array being sorted and therefore one does not need to search in both sub-trees for each recursive call. One either goes left or right on the array. So instead of T(n) = 2T(n/2) + c one would have T(n) = T(n/2) + c.

Now your problem is different from a binary search, because you want to find a position on an array that matches its indices value. So, unlike the binary search in this context you might have to go both right and left as well in some recursive calls.

So in your case the worst case scenario is actually O(N), since 2^(log2N) is N as you can see here. Unless, there is a super clever way of improving your code, I would just go for a normal search, simpler and more readable code for a worst-case scenario of O(N) as well.

You search from the beginning of the array if the value x matches the index you return that value. Otherwise, if x > the current index, you can jump to the next index equals to the value x (i.e., array[x]), thus you skip array position that based on the fact that the array is sorted will not have an index matching its value.

Collectives™ on Stack Overflow

Time complexity of finding index equal to array (sorted) value

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related