Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Introduction to Algorithms Algorithms in Code Recursive Binary Search

Calvin Secrest
Calvin Secrest
24,815 Points
Posted by Calvin Secrest
Calvin Secrest
24,815 Points

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

Victor Mercier
Victor Mercier
14,667 Points

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.

Calvin Secrest
Calvin Secrest
24,815 Points
Calvin Secrest
Calvin Secrest
24,815 Points

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)
Paul Brubaker
Paul Brubaker
14,290 Points
Paul Brubaker
Paul Brubaker
14,290 Points

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.