Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science Introduction to Algorithms Algorithms in Code Recursive Binary Search

Recursive Binary Search

Can someone explain why the Recursive Binary Search algorithm in this video is not Quasilinear Time - O(n log n): Given a data set of size n, the algorithm executes an n number of operations where each operation runs in log n (logarithmic) time.

For example:

if list[midpoint] == target:
      return True
    else:
      if list[midpoint] < target:
        return recursive_binary_search(list[midpoint+1:], target)
      else:return recursive_binary_search(list[:midpoint], target)

Gives us the list at midpoint but then splitting the list into sublists or series of the same statements and the array is smaller each time usually by half. What is the amount of operations this function could take, or can it have a step that takes O(n log n) time?

video: https://teamtreehouse.com/library/recursive-binary-search

Thanks!

2 Answers

No your are wrong, your algorithm will perform O(1) in the best-case scenario and will usually have to make O(log(n)) recursive calls for finding your number.

So algorithm has two steps, one that takes constant time O(1), one that takes logarithmic time O(log n) for the sub list what would be worst case scenario? Is that still linear because of the sub list, what is the overall runtime of the algorithm? Thanks!

Full code Snippet

def recursive_binary_search(list, target):
  if len(list) == 0:
    return False
  else:
    midpoint = (len(list))//2

    if list[midpoint] == target:
      return True
    else:
      if list[midpoint] < target:
        return recursive_binary_search(list[midpoint+1:], target)
      else:return recursive_binary_search(list[:midpoint], target)

def verify(result):
  print("Target found: ", result)

numbers = [1,2,3,4,5,6,7,8]
result = recursive_binary_search(numbers, 12)
verify(result)

result = result = recursive_binary_search(numbers, 6)
verify(result)

The statement

" Given a data set of size n, the algorithm executes n number of operations where each operation runs in log n (logarithmic) time."

is incorrect. In fact, the algorithm consists of O(log(n)) function calls, and within each of these function calls there are k constant time operations, at no point in the algorithm is there a linear time operation. With the caveat that this is not a mathematically rigorous explanation, you can think of an arithmetic where sequential operations have their time complexities summed and nested operations have their time complexities multiplied, to come up with an overall time complexity. In the arithmetic of big O notation, a constant plus a constant is still just a constant, and a constant times a function of n is just that function of n. If one writes out a mathematical expression for our algorithm's time complexity, the constants make their way to the outside of the expression and are simplified away. I don't think counting the actual number of operations this algorithm takes to complete for a given n is really in the spirit of big O notation or this lesson, but I suppose you could do it if you really felt like it.