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.
Calvin Secrest24,812 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.
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?
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.
" 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.