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

Runtime of creating a new list with each recursive call.

When the recursive_binary_search function is called, the instructor is creating a new array with half the list. This isn't an O(1) operation, but it's also not an O(n) operation. The array is smaller each time usually by half.

If that's the case isn't the solution in the video here https://teamtreehouse.com/library/recursive-binary-search an O(log(n)^log(n)) since the log(n) amount of operations this function could take, has a step that takes log(n) time?

2 Answers

No, the time complexity is O(log(n)).

In the video titled "Determining Complexity," he says something that is a bit confusing due to semantics, but he meant that the overall task of splitting the list into sublists (which is basically a series of the same statement) has O(log(n)) time complexity, NOT that each splitting step has O(log(n)) time complexity. The sentence he says immediately after clarifies (not well, but it does half-explicitly say) that he meant that the OVERALL task of splitting of the list into sublists UNTIL A SINGLE-ELEMENT SUBLIST IS REACHED has time complexity of O(log(n)).

For a bottom-up view: splitting a list up in halves per se is simple and takes about a second. However, splitting it up until you get to a single unit takes more time and follows the following pattern. Say your list has 16 items. Your first split yields lists of 8 items each. Your second split of (one of) the resultant lists gives you lists of 4 items each. Third, 2 items each. Fourth and finally, 1 item each. If each split took a second, then starting with a 16-element list would take four seconds to split UNTIL YOU YIELD A LIST OF ONE ELEMENT. If your original list had 128 items, the splits would result in:

  1. 64 items
  2. 32 items
  3. 16 items
  4. 8 items
  5. 4 items
  6. 2 items
  7. 1 item

This means the overall runtime would be seven seconds. From these two examples, we see that the runtime of halving the lists until a single-element list is reached correlates to log2(n), where n is the size of the original list. In other words, the time complexity for splitting either list until a single-element list is achieved is O(log(n)).

Note that time complexity means the DEGREE of the time cost and while related to runtime, is NOT synonymous with runtime, which is literally the time it takes for a given program to run.

~ ~ ~

For comprehensiveness, the stuff below addresses other parts of the algorithm that you don't necessarily have a problem with: The other two statements (finding the midpoint and comparing to the target) each have time complexities of O(1), so overall, these steps have a time complexity that also rings in at O(1). That is, the degree of time complexity is the same, albeit that the runtime itself of the set of these statements adds up to a larger constant than any single execution of one of these statements.

Recalling the triathlon analogy, the upper bound of the time complexity of a function overall is determined by the time complexity of the statement that has the largest time complexity. For this function, the largest time complexity is O(log(n)), so the function's time complexity is O(log(n)).

After going to the next section I can see there is a better solution.

Here is my implementation of the recursive solution in javascript

function recursiveBinarySearch(list, target, first = 0, last = list.length - 1) {
    const mid = Math.floor((first + last) / 2)
    if (list[mid] === target)
        return mid;
    if (first === last)
        return null;

    if (list[mid] < target)
        return recursiveBinarySearch(list, target, mid + 1, last);
    return recursiveBinarySearch(list, target, first, mid);
}