CODEWITHSUNDEEP
pythonalgorithmrecursioniterationbinary-search
minyatur
minyatur

Reputation: 175

what is the difference between iterative and recursive binary search algorithms in case of asymptotic analysis

I need to show the differences between the iterative and the recursive binary search algorithms' asymptotic runtime analysis'. as far as i know, they have the same worst case complexity (O(log(n)) but in some resources it says that recursive has O(log(n)+1). I am a bit confused, can somebody help me about this situation?

I also need to improve a python recursive binary search algorithm to run in just as equal time as the iterative one. the code is written below.

thanks!

def binarySearch(alist,item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)/2
        if alist[midpoint] == item:
            return True
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
            else:
                return binarySearch(alist[midpoint+1:],item)

Upvotes: 3

Views: 5107

Answers (1)

Devin Jeanpierre
Devin Jeanpierre

Reputation: 95596

O(log(n) + 1) is the same as O(log(n)) -- asymptotically, they produce the same set of functions. The constant addition is ignored, just like constant multiples.

They are different in terms of usage of space -- recursive binary search will use log(n) space (because of the stack) unless the tail-calls are removed by the compiler and turned into a non-recursive definition.

Anyway, your algorithm loses out significantly in performance because slicing is very expensive (O(n)).

Upvotes: 2

Related Questions