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 trialCalvin Secrest
24,815 PointsRecursive 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
14,667 PointsNo 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.
Paul Brubaker
14,290 PointsThe 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.
Calvin Secrest
24,815 PointsCalvin Secrest
24,815 PointsSo 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